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 19 ^{th} 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