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:
CQKnPClass is abstract class with pure virtual methods, so that you cannot declare objects of type CQKnPClass, but only of derived classes of its. CQKnPClass offers a general interface for CQKnP solver codes, with methods for setting and reading the data of the problems, for solving it and retrieving solution informations, and so on. The actual CQKnP solvers distributed in this package conforms with the interface, i.e., they derive from CQKnPClass; however, the idea is that applications using this interface would require almost no changes if any other solvers implementing the interface is used. Carefully read the public interface of the class to understand how to use the public methods of the class.
DualCQKnP implements a CQKnP solver based on the standard dual-ascent approach. This class derives from CQKnPClass, hence most of its interface is defined and discussed in CQKnPClass.h; however, for efficiency it is actually restricted to instances where \e all items have strictly positive quadratic costs and finite bounds (both lower and upper), so in fact it does not fully implement the interface.
ExDualCQKnP, derived from DualCQKnP (and hence from CQKnPClass) and extending it to support all the features of the problem (possibly zero quadratic costs, possibly infinite upper and lower bounds). It is slightly less efficient, so DualCQKnP should be preferred for the instances that it can solve.
CQKnPCplex, implementing a CQKnP solver conforming to the CQKnPClass interface based on calls to the commercial (but now free for academic purposes) Cplex solver from IBM. You need to separately obtain a Cplex distribution and link it with this code to make it work. This does not make much of a sense in that Cplex is far slower than the other options, unless one is interested in checking correctness and efficiency of some CQKnP solver.
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].
[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