Limbo
|
Solve multiple knapsack problem with lagrangian relaxation. More...
#include <MultiKnapsackLagRelax.h>
Classes | |
struct | CapacityConstraintPred |
Predicate whether a constraint is a capacity constraint. More... | |
struct | CompareVariableByCoefficient |
Predicate to sort variables according to their coefficient from small to large. More... | |
Public Types | |
typedef LinearModel< T, V > | model_type |
linear model type for the problem | |
typedef model_type::coefficient_value_type | coefficient_value_type |
typedef model_type::variable_value_type | variable_value_type |
typedef model_type::variable_type | variable_type |
typedef model_type::constraint_type | constraint_type |
typedef model_type::expression_type | expression_type |
typedef model_type::term_type | term_type |
typedef model_type::property_type | property_type |
typedef MatrixCSR < coefficient_value_type, int, 1 > | matrix_type |
typedef LagMultiplierUpdater < coefficient_value_type > | updater_type |
typedef ProblemScaler < coefficient_value_type, variable_value_type > | scaler_type |
typedef FeasibleSearcher < coefficient_value_type, variable_value_type > | searcher_type |
Public Member Functions | |||
MultiKnapsackLagRelax (model_type *model) | |||
constructor More... | |||
MultiKnapsackLagRelax (MultiKnapsackLagRelax const &rhs) | |||
copy constructor More... | |||
MultiKnapsackLagRelax & | operator= (MultiKnapsackLagRelax const &rhs) | ||
assignment More... | |||
~MultiKnapsackLagRelax () | |||
destructor | |||
SolverProperty | operator() (updater_type *updater=NULL, scaler_type *scaler=NULL, searcher_type *searcher=NULL) | ||
API to run the algorithm. More... | |||
unsigned int | maxIterations () const | ||
void | setMaxIterations (unsigned int maxIter) | ||
set maximum iterations More... | |||
bool | useInitialSolutions () const | ||
void | setUseInitialSolutions (bool f) | ||
set whether use initial solutions More... | |||
bool | lagObjFlag () const | ||
void | setLagObjFlag (bool f) | ||
set evaluating objective of lagrangian subproblem in each iteration | |||
unsigned int | numNegativeSlackConstraints (bool evaluateFlag) | ||
get number of constraints with negative slackness in current iteration More... | |||
print functions for debug | |||
print variable groups to file
| |||
bool | printVariableGroup (std::string const &filename) const | ||
std::ostream & | printVariableGroup (std::ostream &os=std::cout) const | ||
print variable groups More... | |||
bool | printObjCoef (std::string const &filename) const | ||
print coefficients of variables in objective to file More... | |||
std::ostream & | printObjCoef (std::ostream &os=std::cout) const | ||
print coefficients of variables in objective More... | |||
bool | printLagMultiplier (std::string const &filename) const | ||
print lagrangian multipliers to file More... | |||
std::ostream & | printLagMultiplier (std::ostream &os=std::cout) const | ||
print lagrangian multipliers More... | |||
std::ostream & | printConstraint (std::ostream &os, std::string const &name) const | ||
print constraint More... | |||
template<typename TT > | |||
void | printArray (unsigned int n, TT const *array, bool nonzeroFlag) const | ||
print array More... | |||
Protected Member Functions | |
void | copy (MultiKnapsackLagRelax const &rhs) |
copy object | |
void | destroy () |
destroy model | |
SolverProperty | solve (updater_type *updater, scaler_type *scaler, searcher_type *searcher) |
kernel function to solve the problem More... | |
SolverProperty | solveSubproblems (updater_type *updater, unsigned int beginIter, unsigned int endIter) |
kernel lagrangian iterations More... | |
void | scale (scaler_type *scaler) |
scale problem for better numerical instability More... | |
void | unscale () |
recover problem from scaling | |
void | prepare () |
prepare weights of variables in objective and classify constraints by marking capacity constraints and single item constraints | |
void | updateLagMultipliers (updater_type *updater) |
update lagrangian multipliers More... | |
void | solveLag () |
solve lagrangian subproblem | |
void | computeSlackness () |
compute slackness in an iteration | |
coefficient_value_type | evaluateLagObjective () const |
evaluate objective of the lagrangian subproblem | |
SolverProperty | converge () |
check convergence of current solution More... | |
SolverProperty | postProcess (updater_type *updater, searcher_type *searcher, SolverProperty status) |
post process solution if failed to converge to OPTIMAL after maximum iteration. It choose the best feasible solutions in store More... | |
template<typename TT , typename VV > | |
void | bMinusAx (matrix_type const &A, VV const *x, TT const *b, TT *y) const |
function to compute \(b-Ax\) More... | |
Protected Attributes | |
model_type * | m_model |
model for the problem | |
coefficient_value_type * | m_vObjCoef |
coefficients variables in objective | |
matrix_type | m_constrMatrix |
constraint matrix \(A\) | |
coefficient_value_type * | m_vConstrRhs |
constraint right hand side \(b\) | |
variable_type * | m_vGroupedVariable |
array of grouped variables according to item | |
unsigned int * | m_vVariableGroupBeginIndex |
begin index of grouped variable | |
unsigned int | m_numGroups |
number of groups | |
std::vector< unsigned int > | m_vConstraintPartition |
indices of constraints, the first partition is capacity constraints | |
coefficient_value_type * | m_vLagMultiplier |
array of lagrangian multipliers | |
coefficient_value_type * | m_vNewLagMultiplier |
array of new lagrangian multipliers, temporary storage | |
coefficient_value_type * | m_vSlackness |
array of slackness values in each iteration, \( b-Ax \) | |
std::vector < coefficient_value_type > | m_vScalingFactor |
scaling factor for constraints and objective, last entry is for objective | |
coefficient_value_type | m_objConstant |
constant value in objective from lagrangian relaxation | |
coefficient_value_type | m_lagObj |
current objective of the lagrangian subproblem | |
bool | m_lagObjFlag |
whether evaluate objective of the lagrangian subproblem in each iteration | |
unsigned int | m_iter |
current iteration | |
unsigned int | m_maxIters |
maximum number of iterations | |
bool | m_useInitialSol |
whether use initial solutions or not | |
std::vector< variable_value_type > | m_vBestVariableSol |
best feasible solution found so far | |
coefficient_value_type | m_bestObj |
best objective found so far | |
Friends | |
class | FeasibleSearcher< coefficient_value_type, variable_value_type > |
Solve multiple knapsack problem with lagrangian relaxation.
Suppose we have a set of item \(C\) and a set of knapsack \(B\). Use \(x_{ij}\) to denote item \(i\) is assigned to knapsack \(j\). The primal problem \(P\) is as follows,
\begin{eqnarray*} & min. & \sum_{i,j} c_{ij} \cdot x_{ij}, \\ & s.t. & \sum_{i} a_i x_{ij} \le b_j, \forall j \in B, \\ & & \sum_{j} x_{ij} = 1, \forall i \in C, \\ & & x_{ij} \in \{0, 1\}, \forall i \in C, j \in B. \end{eqnarray*}
The procedure to solve the problem is to iteratively solve following lagrangian subproblem \(L\),
\begin{eqnarray*} & min. & \sum_{i,j} c_{ij} \cdot x_{ij} + \sum_{j} \lambda_j (\sum_{i} a_i x_{ij} - b_j), \\ & s.t. & \sum_{j} x_{ij} = 1, \forall i \in C, \\ & & x_{ij} \in \{0, 1\}, \forall i \in C, j \in B. \end{eqnarray*}
where the subproblem can be solved simply by sorting the weight of \(x_{ij}\) and pick the ones with least cost in each iteration. However, it is difficult to check optimality conditions. So we track the evolution of capacity violations and stop once we observe no significant improvement. The rest violations are solved by heuristic approaches.
T | coefficient type |
V | variable type |
Definition at line 66 of file MultiKnapsackLagRelax.h.
|
inline |
constructor
model | pointer to the model of problem |
Definition at line 87 of file MultiKnapsackLagRelax.h.
|
inline |
copy constructor
rhs | right hand side |
Definition at line 119 of file MultiKnapsackLagRelax.h.
|
protected |
function to compute \(b-Ax\)
TT | coefficient value type |
VV | variable value type |
A | matrix |
x | vector |
b | vector |
y | output vector |
|
protected |
check convergence of current solution
Definition at line 743 of file MultiKnapsackLagRelax.h.
bool limbo::solvers::MultiKnapsackLagRelax< T, V >::lagObjFlag | ( | ) | const |
Definition at line 352 of file MultiKnapsackLagRelax.h.
unsigned int limbo::solvers::MultiKnapsackLagRelax< T, V >::maxIterations | ( | ) | const |
Definition at line 332 of file MultiKnapsackLagRelax.h.
unsigned int limbo::solvers::MultiKnapsackLagRelax< T, V >::numNegativeSlackConstraints | ( | bool | evaluateFlag | ) |
get number of constraints with negative slackness in current iteration
evaluateFlag | if true, recompute slackness for each constraint |
Definition at line 362 of file MultiKnapsackLagRelax.h.
|
inline |
API to run the algorithm.
updater | an object to update lagrangian multipliers, use default updater if NULL |
scaler | an object to scale constraints and objective, use default scaler if NULL |
searcher | an object to search for feasible solutions, use default searcher if NULL |
Definition at line 142 of file MultiKnapsackLagRelax.h.
|
inline |
|
protected |
post process solution if failed to converge to OPTIMAL after maximum iteration. It choose the best feasible solutions in store
updater | an object to update lagrangian multipliers |
status | current status of solutions |
searcher | an object to search for feasible solutions |
Definition at line 785 of file MultiKnapsackLagRelax.h.
void limbo::solvers::MultiKnapsackLagRelax< T, V >::printArray | ( | unsigned int | n, |
TT const * | array, | ||
bool | nonzeroFlag | ||
) | const |
print array
TT | array data type |
n | dimension |
array | array |
nonzeroFlag | whether only dump nonzero elements |
Definition at line 905 of file MultiKnapsackLagRelax.h.
std::ostream & limbo::solvers::MultiKnapsackLagRelax< T, V >::printConstraint | ( | std::ostream & | os, |
std::string const & | name | ||
) | const |
print constraint
os | output stream |
name | constraint name |
Definition at line 889 of file MultiKnapsackLagRelax.h.
bool limbo::solvers::MultiKnapsackLagRelax< T, V >::printLagMultiplier | ( | std::string const & | filename | ) | const |
print lagrangian multipliers to file
filename | output file name |
Definition at line 866 of file MultiKnapsackLagRelax.h.
std::ostream & limbo::solvers::MultiKnapsackLagRelax< T, V >::printLagMultiplier | ( | std::ostream & | os = std::cout | ) | const |
print lagrangian multipliers
os | output stream |
Definition at line 879 of file MultiKnapsackLagRelax.h.
bool limbo::solvers::MultiKnapsackLagRelax< T, V >::printObjCoef | ( | std::string const & | filename | ) | const |
print coefficients of variables in objective to file
filename | output file name |
Definition at line 843 of file MultiKnapsackLagRelax.h.
std::ostream & limbo::solvers::MultiKnapsackLagRelax< T, V >::printObjCoef | ( | std::ostream & | os = std::cout | ) | const |
print coefficients of variables in objective
os | output stream |
Definition at line 856 of file MultiKnapsackLagRelax.h.
std::ostream & limbo::solvers::MultiKnapsackLagRelax< T, V >::printVariableGroup | ( | std::ostream & | os = std::cout | ) | const |
print variable groups
os | output stream |
Definition at line 824 of file MultiKnapsackLagRelax.h.
|
protected |
scale problem for better numerical instability
scaler | an object to scale constraints and objective, use default scaler if NULL |
Definition at line 536 of file MultiKnapsackLagRelax.h.
void limbo::solvers::MultiKnapsackLagRelax< T, V >::setMaxIterations | ( | unsigned int | maxIter | ) |
set maximum iterations
maxIter | maximum iterations |
Definition at line 337 of file MultiKnapsackLagRelax.h.
void limbo::solvers::MultiKnapsackLagRelax< T, V >::setUseInitialSolutions | ( | bool | f | ) |
set whether use initial solutions
f | flag |
Definition at line 347 of file MultiKnapsackLagRelax.h.
|
protected |
kernel function to solve the problem
updater | an object to update lagrangian multipliers |
scaler | an object to scale constraints and objective, use default scaler if NULL |
searcher | an object to search for feasible solutions, use default searcher if NULL |
Definition at line 455 of file MultiKnapsackLagRelax.h.
|
protected |
kernel lagrangian iterations
updater | an object to update lagrangian multipliers |
beginIter | begin iteration number |
endIter | end iteration number |
Definition at line 509 of file MultiKnapsackLagRelax.h.
|
protected |
update lagrangian multipliers
updater | an object to update lagrangian multipliers |
Definition at line 673 of file MultiKnapsackLagRelax.h.
bool limbo::solvers::MultiKnapsackLagRelax< T, V >::useInitialSolutions | ( | ) | const |
Definition at line 342 of file MultiKnapsackLagRelax.h.