The CQKnPClass Project

The CQKnPClass Project aims at distributing efficient tools for the solution of Continuous (Convex) Quadratic Knapsack Problems, (CQKnP), i.e., optimization problems with n variables, only one constraint, and convex quadratic objective function. These problems are very easy, but they typically need to be solved very many times within approaches to more complex problems. This also happens surprisingly often and in very diverse applications such as Lagrangian heuristics for ramp-constrained Unit Commitment problems in electrical power production [FrGL06], 1-D sensor placement problems [FGGP11], and deflected subgradient approaches [dAFr09] for Multicommodity Min-Cost Flow Problems [KeSh77, Software, Data].

We are distributing a reasonably efficient implementation of the simplest approach to the problem, based on forming the Lagrangian Dual of the only constraint and solving the corresponding univariate maximization. This is easily done once the set of possible breakpoints of the Lagrangian function (which is piecewise-quadratic and concave) is properly sorted, and therefore on O(n log n). Thus sorting (and re-sorting in case of changes in the data of the instance) is the bottleneck operation, and therefore a few options exist for doing it efficiently. The current distribution is organized around four classes:

A small extra class CQKnPClone, is also provided which implements a "fake" C QKnP solver that takes two "real" ones and does everything on both; this is useful for testing the solvers (either for correctness or for efficiency) when used within "complex" approaches.

All these can be downloaded from GitHub. This code is provided free of charge under the "GNU Lesser General Public License", and it is provided "as is", without any explicit or implicit warranty that it will properly behave or it will suit you needs: see the file doc/LGPL.txt in the distribution and the Reference Manual for all details of the rights and duties you have about this code. More details about the code and the computational results can be found in [FrGo13].

Bibliography

[dAFr09] G. d'Antonio, A. Frangioni "Convergence Analysis of Deflected Conditional Approximate Subgradient Methods" SIAM Journal on Optimization 20(1), p. 357 - 386, 2009

[FrGL06] A. Frangioni, C. Gentile, F. Lacalandra "New Lagrangian Heuristics for Ramp-Constrained Unit Commitment Problems" Proceedings of the 19th Mini-EURO Conference in Operational Research Models and Methods in the Energy Sector (ORMMES 2006), Coimbra, 6-8 September 2006

[FGGP11] A. Frangioni, C. Gentile, E. Grande, A. Pacifici "Projected Perspective Reformulations With Applications in Design Problems" Operations Research 59(5), p. 1225 - 1232, 2011

[FrGo13] A. Frangioni, E. Gorgone "A Library for Continuous Convex Separable Quadratic Knapsack Problems" European Journal of Operational Research 229(1), 37–40, 2013

[KeSh77] J. Kennington, M. Shalaby "An Effective Subgradient Procedure for Minimal Cost Multicommodity Flow Problems" Management Science 23(9) p. 994 - 1004, 1977