Optimization Online


On the Coupled Continuous Knapsack Problems: Projection Onto the Volume Constrained Gibbs N-Simplex

Rouhollah Tavakoli (rtavakoli***at***sharif.ir)

Abstract: Coupled continuous quadratic knapsack problems (CCK) are introduced in the present study. The solution of a CCK problem is equivalent to the projection of an arbitrary point onto the volume constrained Gibbs N-simplex, which has a wide range of applications in computational science and engineering. Three algorithms have been developed in the present study to solve large scale CCK problems. According to the numerical experiments of this study, the computational costs of presented algorithms scale linearly with the problem size, when it is sufficiently large. Moreover, they show competitive or even superior computational performance compared to the advanced QP solvers. The ease of implementation and linear scaling of memory usage with the problem size are the other benefits of the presented algorithms.

Keywords: knapsack problem, convex optimization, linearly constrained optimization, time-linear algorithm

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Applications -- OR and Management Sciences


Download: [PDF]

Entry Submitted: 09/02/2013
Entry Accepted: 09/02/2013
Entry Last Modified: 02/16/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society