Solver of Continuous Quadratic Knapsack Problems (CQKnP) based on the standard formulation of the dual problem as a piecewise-convex problem in the unique multiplier of the knapsack constraint and the corresponding obvious dual-ascent approach. More...
#include <DualCQKnP.h>
Public Member Functions | |
| DualCQKnP (const bool sort=true, const double eps=1e-6) | |
| The most important operation for solving the CQKnP with a dual method is the sorting of the items for nondecreasing elements. More... | |
| void | SetSort (const bool WhchSrt=false) |
| Allows to change the sorting procedures to be used in the next calls to SolveKNP(); see the comments to the constructor for details. More... | |
 Public Member Functions inherited from CQKnPClass | |
| virtual void | ReadInstance (std::istream &inFile, bool RBV=false) |
| Read the instance from file. More... | |
| virtual int | KNPn (void) |
| Returns the current number of items. More... | |
| virtual void | WriteInstance (std::ostream &oFile, const int precc=16, const int precv=16) |
| Write the instance to the provided ostream in the "complete" format read by ReadInstance() [see above]. More... | |
Protected Attributes | |
| double * | A |
| vector of lower bounds | |
| double * | B |
| vector of upper bounds | |
| double * | C |
| vector of linear costs | |
| double * | D |
| vector of quadratic costs | |
| double | McB |
| volume value | |
| bool | sense |
| sense of knapsack constraint | |
| double | LB |
| lower bound on dual variable | |
| double | UB |
| upper bound on dual variable | |
| int * | I |
| optimal ordering | |
| int | nSort |
| how many elements we have to sort | |
| double * | OV |
| values upon which to order | |
| double * | XSol |
| primal solution | |
| double | muStar |
| optimal dual solution | |
| bool | WSort |
| which sorting procedure is used | |
| double | OptVal |
| The Optimal Value. | |
| double | DefEps |
| precision required to construct the solution | |
| Protected Attributes inherited from CQKnPClass | |
| int | n |
| total number of items | |
| int | status |
| status of the algorithm: it is an int so that derived classes can use it to encode other information apart from the return value of SolveKNP(). More... | |
Static Protected Attributes | |
| static int * | QSStck |
| the stack to simulate recursive calls in QS | |
| static int | InstCntr |
| number of active instances | |
| static int | maxvl |
| max value of items | |
Additional Inherited Members | |
| Public Types inherited from CQKnPClass |
Detailed Description
Solver of Continuous Quadratic Knapsack Problems (CQKnP) based on the standard formulation of the dual problem as a piecewise-convex problem in the unique multiplier of the knapsack constraint and the corresponding obvious dual-ascent approach.
This class is restricted to instances where all items have strictly positive quadratic costs and finite bounds (both lower and upper).
Derives from CQKnpClass and therefore it mostly conforms to its interface, except for refusing to solve instances without the required characteristics.
Constructor & Destructor Documentation
| DualCQKnP | ( | const bool | sort = true, |
| const double | eps = 1e-6 |
||
| ) |
The most important operation for solving the CQKnP with a dual method is the sorting of the items for nondecreasing elements.
2 * A[ i ] * D[ i ] + C[ i ] and 2 * B[ i ] * D[ i ] + C[ i ].
If the knapsack is a large one, this can be (relatively) time-consuming. Different sort procedures can be better in different situations, and the parameter 'sort' allows to decide which among the available sorting procedures has to be used. Possible values of this parameter are:
false Bubble Sort: this is O( n^2 ) on average, but it can be very fast - O( n ) - if reoptimizing from a previous problem where the order was not very different (e.g., only few costs have changed).
true [default] Quick Sort: this is O( n lg n ) on average and pretty efficient in practice, but can be very slow - O( n^2 ) - if the vector is already (almost) ordered, e.g. when reoptimizing from a previous problem where only few costs have changed.
The parameter Eps defines the precision required to construct the solution [default value is 1e-6].
The choices can be changed at any time with SetSort() and SetEps(), respectively [see below].
Member Function Documentation
|
inline |
Allows to change the sorting procedures to be used in the next calls to SolveKNP(); see the comments to the constructor for details.
References DualCQKnP::A, DualCQKnP::B, DualCQKnP::C, DualCQKnP::D, DualCQKnP::DefEps, DualCQKnP::McB, and DualCQKnP::WSort.
