7 #ifndef LIMBO_SOLVERS_MULTIKNAPSACKLAGRELAX_H
8 #define LIMBO_SOLVERS_MULTIKNAPSACKLAGRELAX_H
26 template <
typename T,
typename V>
28 template <
typename T,
typename V>
30 template <
typename T,
typename V>
32 template <
typename T,
typename V>
65 template <
typename T,
typename V>
144 return solve(updater, scaler, searcher);
171 bool printVariableGroup(std::string
const& filename)
const;
175 std::ostream& printVariableGroup(std::ostream& os = std::cout)
const;
183 std::ostream&
printObjCoef(std::ostream& os = std::cout)
const;
196 std::ostream&
printConstraint(std::ostream& os, std::string
const& name)
const;
202 template <
typename TT>
203 void printArray(
unsigned int n, TT
const* array,
bool nonzeroFlag)
const;
219 return constr.
sense() !=
'=';
244 bool operator()(variable_type
const& v1, variable_type
const& v2)
const
246 return vObjCoef[v1.
id()] < vObjCoef[v2.
id()];
267 void scale(scaler_type* scaler);
298 template <
typename TT,
typename VV>
299 void bMinusAx(matrix_type
const& A, VV
const* x, TT
const* b, TT* y)
const;
331 template <
typename T,
typename V>
336 template <
typename T,
typename V>
339 m_maxIters = maxIters;
341 template <
typename T,
typename V>
344 return m_useInitialSol;
346 template <
typename T,
typename V>
351 template <
typename T,
typename V>
356 template <
typename T,
typename V>
361 template <
typename T,
typename V>
364 unsigned int result = 0;
368 result += (m_vSlackness[i] < 0)? 1 : 0;
371 template <
typename T,
typename V>
381 m_vObjCoef =
new coefficient_value_type [m_model->numVariables()];
387 m_vConstrRhs =
new coefficient_value_type [m_constrMatrix.numRows];
396 m_vVariableGroupBeginIndex =
new unsigned int [m_numGroups+1];
404 m_vLagMultiplier =
new coefficient_value_type [m_constrMatrix.numRows];
406 m_vNewLagMultiplier =
new coefficient_value_type [m_constrMatrix.numRows];
408 m_vSlackness =
new coefficient_value_type [m_constrMatrix.numRows];
421 template <
typename T,
typename V>
425 if (m_vGroupedVariable)
427 delete [] m_vGroupedVariable;
428 delete [] m_vVariableGroupBeginIndex;
429 m_vGroupedVariable = NULL;
430 m_vVariableGroupBeginIndex = NULL;
434 delete [] m_vObjCoef;
437 m_constrMatrix.reset();
440 delete [] m_vConstrRhs;
444 if (m_vLagMultiplier)
446 delete [] m_vLagMultiplier;
447 delete [] m_vNewLagMultiplier;
448 delete [] m_vSlackness;
449 m_vLagMultiplier = NULL;
450 m_vNewLagMultiplier = NULL;
454 template <
typename T,
typename V>
457 bool defaultUpdater =
false;
458 bool defaultScaler =
false;
459 bool defaultSearcher =
false;
464 defaultUpdater =
true;
470 defaultScaler =
true;
473 if (searcher == NULL)
476 defaultSearcher =
true;
491 status = postProcess(updater, searcher, status);
508 template <
typename T,
typename V>
513 for (m_iter = beginIter; m_iter < endIter; ++m_iter)
515 if (!useInitialSolutions() || m_iter != 0)
518 #ifdef DEBUG_MULTIKNAPSACKLAGRELAX
519 limboPrint(kDEBUG,
"iteration %u with %u negative slacks, %g lagrangian objective, %g objective\n", m_iter, numNegativeSlackConstraints(
false), evaluateLagObjective(), m_model->evaluateObjective());
522 std::ofstream out (buf);
524 printLagMultiplier(out);
527 if ((status = converge()) ==
OPTIMAL || m_iter+1 == endIter)
530 updateLagMultipliers(updater);
535 template <
typename T,
typename V>
539 m_vScalingFactor.resize(m_model->constraints().size()+1);
541 for (
unsigned int i = 0, ie = m_model->constraints().size(); i < ie; ++i)
543 m_vScalingFactor[i] = scaler->operator()(m_model->constraints()[i]);
544 m_model->scaleConstraint(i, 1.0/m_vScalingFactor[i]);
547 m_vScalingFactor.back() = scaler->operator()(m_model->objective());
548 m_model->scaleObjective(1.0/m_vScalingFactor.back());
550 template <
typename T,
typename V>
554 for (
unsigned int i = 0, ie = m_model->constraints().size(); i < ie; ++i)
555 m_model->scaleConstraint(i, m_vScalingFactor[i]);
557 m_model->scaleObjective(m_vScalingFactor.back());
559 template <
typename T,
typename V>
563 m_vObjCoef =
new coefficient_value_type [m_model->numVariables()];
564 std::fill(m_vObjCoef, m_vObjCoef+m_model->numVariables(), 0);
565 for (
typename std::vector<term_type>::const_iterator it = m_model->objective().terms().begin(), ite = m_model->objective().terms().end(); it != ite; ++it)
566 m_vObjCoef[it->variable().id()] += it->coefficient();
570 for (
unsigned int ie = m_model->numVariables(); i < ie; ++i)
573 variable_value_type lowerBound = m_model->variableLowerBound(var);
574 variable_value_type upperBound = m_model->variableUpperBound(var);
575 if (lowerBound == upperBound)
576 m_model->setVariableSolution(var, lowerBound);
580 m_vConstraintPartition.resize(m_model->constraints().size());
582 for (
unsigned int ie = m_model->constraints().size(); i < ie; ++i)
583 m_vConstraintPartition[i] = i;
584 std::vector<unsigned int>::iterator bound = std::partition(m_vConstraintPartition.begin(), m_vConstraintPartition.end(),
CapacityConstraintPred(m_model->constraints()));
585 unsigned int numCapacityConstraints = std::distance(m_vConstraintPartition.begin(), bound);
586 m_vLagMultiplier =
new coefficient_value_type [numCapacityConstraints];
587 std::fill(m_vLagMultiplier, m_vLagMultiplier+numCapacityConstraints, 0);
588 m_vNewLagMultiplier =
new coefficient_value_type [numCapacityConstraints];
589 std::fill(m_vNewLagMultiplier, m_vNewLagMultiplier+numCapacityConstraints, 0);
590 m_vSlackness =
new coefficient_value_type [numCapacityConstraints];
591 std::fill(m_vSlackness, m_vSlackness+numCapacityConstraints, 0);
594 for (std::vector<unsigned int>::iterator it = m_vConstraintPartition.begin(); it != bound; ++it)
595 m_model->constraints().at(*it).normalize(
'<');
598 m_constrMatrix.numRows = numCapacityConstraints;
599 m_constrMatrix.numColumns = m_model->numVariables();
600 m_constrMatrix.numElements = 0;
602 m_constrMatrix.vRowBeginIndex[0] = matrix_type::s_startingIndex;
606 for (std::vector<unsigned int>::iterator it = m_vConstraintPartition.begin(); it != bound; ++it, ++i)
608 #ifdef DEBUG_MULTIKNAPSACKLAGRELAX
612 m_constrMatrix.vRowBeginIndex[i] = m_constrMatrix.vRowBeginIndex[i-1]+constr.
expression().
terms().size();
615 m_constrMatrix.numElements = m_constrMatrix.vRowBeginIndex[m_constrMatrix.numRows]-matrix_type::s_startingIndex;
618 m_constrMatrix.vElement =
new coefficient_value_type [m_constrMatrix.numElements];
621 for (std::vector<unsigned int>::iterator it = m_vConstraintPartition.begin(); it != bound; ++it)
624 for (
typename std::vector<typename constraint_type::term_type>::const_iterator itt = constr.
expression().
terms().begin(), itte = constr.
expression().
terms().end(); itt != itte; ++itt, ++i)
626 #ifdef DEBUG_MULTIKNAPSACKLAGRELAX
629 m_constrMatrix.vElement[i] = itt->coefficient();
630 m_constrMatrix.vColumn[i] = itt->variable().id()+matrix_type::s_startingIndex;
634 m_vConstrRhs =
new coefficient_value_type [m_constrMatrix.numRows];
636 for (std::vector<unsigned int>::iterator it = m_vConstraintPartition.begin(); it != bound; ++it, ++i)
645 m_numGroups = std::distance(bound, m_vConstraintPartition.end());
646 unsigned int numGroupElements = 0;
647 for (std::vector<unsigned int>::iterator it = bound, ite = m_vConstraintPartition.end(); it != ite; ++it, ++i)
653 m_vVariableGroupBeginIndex =
new unsigned int [m_numGroups+1];
655 m_vVariableGroupBeginIndex[m_numGroups] = numGroupElements;
658 for (std::vector<unsigned int>::iterator it = bound, ite = m_vConstraintPartition.end(); it != ite; ++it, ++i)
661 #ifdef DEBUG_MULTIKNAPSACKLAGRELAX
665 m_vVariableGroupBeginIndex[i] = j;
666 for (
typename std::vector<term_type>::const_iterator itt = expr.terms().begin(), itte = expr.terms().end(); itt != itte; ++itt, ++j)
668 m_vGroupedVariable[j] = itt->variable();
672 template <
typename T,
typename V>
679 updater->operator()(m_iter, m_constrMatrix.numRows, m_vSlackness, m_vLagMultiplier, m_vNewLagMultiplier);
684 axpy(m_constrMatrix.numRows, (coefficient_value_type)-1, m_vLagMultiplier, m_vNewLagMultiplier);
685 ATxPlusy((coefficient_value_type)1, m_constrMatrix, m_vNewLagMultiplier, m_vObjCoef);
686 axpy(m_constrMatrix.numRows, (coefficient_value_type)1, m_vNewLagMultiplier, m_vLagMultiplier);
688 updater->operator()(m_iter, m_constrMatrix.numRows, m_vSlackness, m_vLagMultiplier, m_vLagMultiplier);
690 std::fill(m_vObjCoef, m_vObjCoef+m_model->numVariables(), 0);
691 for (
typename std::vector<term_type>::const_iterator it = m_model->objective().terms().begin(), ite = m_model->objective().terms().end(); it != ite; ++it)
692 m_vObjCoef[it->variable().id()] += it->coefficient();
693 ATxPlusy((coefficient_value_type)1, m_constrMatrix, m_vLagMultiplier, m_vObjCoef);
698 m_objConstant = -
dot(m_constrMatrix.numRows, m_vConstrRhs, m_vLagMultiplier);
701 template <
typename T,
typename V>
706 variable_value_type* vVariableSol = &m_model->variableSolutions()[0];
708 variable_type const* variableGroupBegin = m_vGroupedVariable;
713 std::fill(vVariableSol, vVariableSol+m_model->numVariables(), 0);
714 for (i = 0; i < m_numGroups; ++i)
716 variableGroupBegin = variableGroupEnd;
717 variableGroupEnd = m_vGroupedVariable+m_vVariableGroupBeginIndex[i+1];
719 variable = std::min_element(variableGroupBegin, variableGroupEnd, helper);
720 vVariableSol[variable->
id()] = 1;
724 m_lagObj = evaluateLagObjective();
727 template <
typename T,
typename V>
731 bMinusAx(m_constrMatrix, &m_model->variableSolutions()[0], m_vConstrRhs, m_vSlackness);
733 template <
typename T,
typename V>
737 coefficient_value_type objValue = m_objConstant;
738 for (
unsigned int i = 0, ie = m_model->numVariables(); i < ie; ++i)
739 objValue += m_vObjCoef[i]*m_model->variableSolution(
variable_type(i));
742 template <
typename T,
typename V>
745 bool feasibleFlag =
true;
746 bool convergeFlag =
true;
749 coefficient_value_type multiplier = m_vLagMultiplier[i];
750 coefficient_value_type slackness = m_vSlackness[i];
759 convergeFlag = feasibleFlag =
false;
762 else if (multiplier*slackness != 0)
764 convergeFlag =
false;
771 coefficient_value_type obj = m_model->evaluateObjective();
774 m_vBestVariableSol = m_model->variableSolutions();
784 template <
typename T,
typename V>
791 m_model->variableSolutions() = m_vBestVariableSol;
797 return searcher->operator()(updater);
801 template <
typename T,
typename V>
802 template <
typename TT,
typename VV>
807 AxPlusy((coefficient_value_type)-1, A, x, y);
810 template <
typename T,
typename V>
811 bool MultiKnapsackLagRelax<T, V>::printVariableGroup(std::string
const& filename)
const
813 std::ofstream out (filename.c_str());
819 printVariableGroup(out);
823 template <
typename T,
typename V>
826 os << __func__ <<
" iteration " << m_iter <<
"\n";
827 for (
unsigned int i = 0; i < m_numGroups; ++i)
829 os <<
"[" << i <<
"]";
830 for (
unsigned int j = m_vVariableGroupBeginIndex[i]; j < m_vVariableGroupBeginIndex[i+1]; ++j)
833 if (m_model->variableSolution(*variable) == 1)
834 os <<
" *" << m_model->variableName(*variable) <<
"*";
836 os <<
" " << m_model->variableName(*variable);
842 template <
typename T,
typename V>
845 std::ofstream out (filename.c_str());
855 template <
typename T,
typename V>
858 os << __func__ <<
" iteration " << m_iter <<
"\n";
859 os <<
"lagrangian objective = " << m_lagObj <<
"\n";
860 os <<
"objective = " << m_model->evaluateObjective() <<
"\n";
861 for (
unsigned int i = 0, ie = m_model->numVariables(); i < ie; ++i)
862 os << m_model->variableName(
variable_type(i)) <<
" = " << m_vObjCoef[i] <<
"\n";
865 template <
typename T,
typename V>
868 std::ofstream out (filename.c_str());
874 printLagMultiplier(out);
878 template <
typename T,
typename V>
881 os << __func__ <<
" iteration " << m_iter <<
"\n";
882 for (
int i = 0; i < m_constrMatrix.numRows; ++i)
883 os <<
"[" << m_model->constraintName(m_model->constraints().at(m_vConstraintPartition[i])) <<
"] = " << m_vLagMultiplier[i]
884 <<
" slack = " << m_vSlackness[i]
888 template <
typename T,
typename V>
891 for (
int i = 0; i < this->m_constrMatrix.numRows; ++i)
894 if (m_model->constraintName(constr) == name)
896 os <<
"constraint " << name <<
": rhs = " << constr.
rightHandSide() <<
"\n";
897 for (
typename std::vector<term_type>::const_iterator it = constr.
expression().
terms().begin(), ite = constr.
expression().
terms().end(); it != ite; ++it)
898 os << m_model->variableName(it->variable()) <<
": " << m_model->variableSolution(it->variable()) <<
"*" << it->coefficient() <<
"\n";
903 template <
typename T,
typename V>
904 template <
typename TT>
907 limboPrint(kNONE,
"array of length %u = {", n);
908 for (
unsigned int i = 0; i < n; ++i)
916 limboPrint(kNONE,
"%u:%g", i, (
double)array[i]);
932 template <
typename T>
949 virtual value_type
operator()(
unsigned int iter, value_type multiplier, value_type slackness) = 0;
956 virtual void operator()(
unsigned int iter,
unsigned int n, value_type
const* vSlackness, value_type
const* vLagMultiplier, value_type* vNewLagMultiplier) = 0;
961 template <
typename T>
962 class SubGradientDescent :
public LagMultiplierUpdater<T>
977 ,
m_iter(std::numeric_limits<unsigned int>::
max())
993 this->base_type::operator=(rhs);
1008 value_type
operator()(
unsigned int iter, value_type multiplier, value_type slackness)
1021 void operator()(
unsigned int iter,
unsigned int n, value_type
const* vSlackness, value_type
const* vLagMultiplier, value_type* vNewLagMultiplier)
1025 value_type
const* slackness = vSlackness;
1026 value_type
const* multiplier = vLagMultiplier;
1027 value_type* newMultiplier = vNewLagMultiplier;
1028 for (
unsigned int i = 0; i < n; ++i)
1067 template <
typename T,
typename V>
1098 virtual value_type
operator()(constraint_type
const& constr)
const
1107 template <
typename T,
typename V>
1136 for (
typename std::vector<term_type>::const_iterator it = expr.
terms().begin(), ite = expr.
terms().end(); it != ite; ++it)
1137 result =
std::min(result, it->coefficient());
1155 template <
typename T,
typename V>
1182 value_type result = 0;
1183 for (
typename std::vector<term_type>::const_iterator it = expr.
terms().begin(), ite = expr.
terms().end(); it != ite; ++it)
1184 result += it->coefficient()*it->coefficient();
1185 return sqrt(result/expr.
terms().size());
1199 template <
typename T,
typename V>
1200 class FeasibleSearcher
1300 template <
typename T,
typename V>
1379 std::vector<VariableMoveCost> vVariableMoveCost;
1381 coefficient_value_type largeCost = 0;
1383 largeCost += (*it > 0)? *it : 0;
1388 numNegativeSlacksPrev = numNegativeSlacks;
1389 numNegativeSlacks = 0;
1393 coefficient_value_type slackness = this->
m_vSlackness[i];
1401 std::sort(vVariableMoveCost.begin(), vVariableMoveCost.end(), CompareVariableMoveCost());
1404 for (
typename std::vector<VariableMoveCost>::const_iterator it = vVariableMoveCost.begin(), ite = vVariableMoveCost.end(); it != ite; ++it)
1410 this->
m_vObjCoef[it->variable.id()] = largeCost;
1412 slackness += it->capacity;
1414 vVariableProcess[it->variable.id()] =
true;
1419 ++numNegativeSlacks;
1422 if (numNegativeSlacks == 0)
1426 }
while (numNegativeSlacks && numNegativeSlacks*(1+
m_convergeRatio) < numNegativeSlacksPrev);
1437 for (
unsigned int i = 0; i < this->
m_numGroups; ++i)
1440 variable_type
const* ite = this->
m_vGroupedVariable+this->m_vVariableGroupBeginIndex[i+1];
1441 for (; it != ite; ++it)
1451 void computeMoveCost(constraint_type
const& constr, std::vector<bool>
const& vVariableProcess, std::vector<VariableMoveCost>& vVariableMoveCost)
const
1454 vVariableMoveCost.clear();
1456 for (
typename std::vector<term_type>::const_iterator it = constr.
expression().
terms().begin(), ite = constr.
expression().
terms().end(); it != ite; ++it, ++j)
1465 variable_type
const* itve = this->
m_vGroupedVariable+this->m_vVariableGroupBeginIndex[group+1];
1466 for (; itv != itve; ++itv)
1468 if (it->variable() != *itv)
1474 vVariableMoveCost.push_back(VariableMoveCost(it->variable(), moveCost, it->coefficient()));
1486 template <
typename T,
typename V>
1524 , targetVariable(targetVar)
1556 return vSlackness[i] < vSlackness[j];
1578 std::vector<VariableMoveCost> vVariableMoveCost;
1580 std::vector<unsigned int> vNegativeSlackConstr;
1585 coefficient_value_type slackness = this->
m_vSlackness[i];
1587 vNegativeSlackConstr.push_back(i);
1591 std::sort(vNegativeSlackConstr.begin(), vNegativeSlackConstr.end(), CompareConstraintSlack(this->
m_vSlackness));
1594 for (std::vector<unsigned int>::const_iterator it = vNegativeSlackConstr.begin(), ite = vNegativeSlackConstr.end(); it != ite; ++it)
1601 vVariableMoveCost.clear();
1604 typename std::vector<VariableMoveCost>::const_iterator itm = std::min_element(vVariableMoveCost.begin(), vVariableMoveCost.end(), CompareVariableMoveCost());
1611 variable_type
const& var = itm->variable;
1616 term_type
const& curTerm = curConstr.
expression().
terms()[itc->second];
1617 coefficient_value_type& curSlackness = this->
m_vSlackness[itc->first];
1622 variable_type
const& targetVar = itm->targetVariable;
1624 for (std::vector<std::pair<unsigned int, unsigned int> >::const_iterator itc = this->
m_mVariable2Constr[targetVar.
id()].begin(), itce = this->
m_mVariable2Constr[targetVar.
id()].end(); itc != itce; ++itc)
1627 term_type
const& curTerm = curConstr.
expression().
terms()[itc->second];
1628 coefficient_value_type& curSlackness = this->
m_vSlackness[itc->first];
1638 for (std::vector<unsigned int>::const_iterator it = vNegativeSlackConstr.begin(), ite = vNegativeSlackConstr.end(); it != ite; ++it)
1657 for (
typename std::vector<term_type>::const_iterator it = constr.
expression().
terms().begin(), ite = constr.
expression().
terms().end(); it != ite; ++it, ++j)
1668 void computeMoveCost(constraint_type
const& constr, std::vector<VariableMoveCost>& vVariableMoveCost)
const
1671 vVariableMoveCost.clear();
1673 for (
typename std::vector<term_type>::const_iterator it = constr.
expression().
terms().begin(), ite = constr.
expression().
terms().end(); it != ite; ++it, ++j)
1675 variable_type
const& var = it->variable();
1681 variable_type targetVar;
1684 variable_type
const* itve = this->
m_vGroupedVariable+this->m_vVariableGroupBeginIndex[group+1];
1685 for (; itv != itve; ++itv)
1690 bool enoughCapacityFlag =
true;
1693 coefficient_value_type slackness = this->
m_vSlackness[itc->first];
1694 coefficient_value_type coeff = this->
m_model->
constraints()[itc->first].expression().terms()[itc->second].coefficient();
1695 if (slackness < coeff)
1697 enoughCapacityFlag =
false;
1701 if (!enoughCapacityFlag)
1704 if (moveCost > targetCost)
1706 moveCost = targetCost;
1712 vVariableMoveCost.push_back(VariableMoveCost(var, targetVar, moveCost));
1724 template <
typename T,
typename V>
~MultiKnapsackLagRelax()
destructor
model_type::term_type term_type
term type
std::vector< unsigned int > m_vVariable2Group
map variables to groups
SearchByAdjustCoefficient< T, V > base_type
base type
Scaling scheme with minimum coefficient in an expression.
coefficient_value_type const * vSlackness
array of slackness
solver_type::matrix_type matrix_type
matrix type
variable_value_type variableSolution(variable_type const &var) const
solver_type::updater_type updater_type
updater type for lagrangian multipliers
variable_type targetVariable
variable of the item for the target bin
Base heuristic to search for feasible solutions.
~SearchByCombinedStrategy()
destructor
MultiKnapsackLagRelax(MultiKnapsackLagRelax const &rhs)
copy constructor
Describe properties of a variable.
std::vector< unsigned int > m_vConstraintPartition
indices of constraints, the first partition is capacity constraints
bool m_lagObjFlag
whether evaluate objective of the lagrangian subproblem in each iteration
base_type::model_type model_type
model type
~MinCoefficientScaler()
destructor
SolverProperty
Some enums used in solver.
FeasibleSearcher(solver_type *solver)
constructor
SolverProperty solveSubproblems(updater_type *updater, unsigned int beginIter, unsigned int endIter)
kernel lagrangian iterations
value_type operator()(expression_type const &expr) const
API to compute scaling factor for expression using L2 norm.
unsigned int m_maxIters
maximum number of iterations
model_type::coefficient_value_type coefficient_value_type
coefficient value type
bool useInitialSolutions() const
int limboSPrint(MessageType m, char *buf, const char *format,...)
formatted print with prefix to buffer
ProblemScaler< T, V > base_type
base type
base_type::term_type term_type
term type
SearchByCombinedStrategy(solver_type *solver, coefficient_value_type convergeRatio=0.1)
constructor
variable_type variable
variable of the item
coefficient_value_type coefficient() const
LinearModel< T, V > model_type
linear model type for the problem
coefficient_value_type *& m_vLagMultiplier
array of lagrangian multipliers
std::vector< coefficient_value_type > m_vObjCoefOrig
original coefficient of variable in objective
model_type::variable_value_type variable_value_type
variable value type
model_type::constraint_type constraint_type
constraint type
void reset()
Destroy matrix and recycle memory.
coefficient_value_type *const & m_vConstrRhs
constraint right hand side
unsigned int *const & m_vVariableGroupBeginIndex
begin index of grouped variable
model_type::term_type term_type
term type
Basic utilities such as variables and linear expressions in solvers.
void computeSlackness()
compute slackness in an iteration
virtual value_type operator()(expression_type const &) const
API to compute scaling factor for expression using L2 norm.
LinearModel< T, V > model_type
model type
base_type::term_type term_type
term type
bool is_integer(string const &s)
check whether string represents an integer
Predicate to sort variables according to their coefficient from small to large.
model_type *const & m_model
model for the problem
~SearchByAdjustCoefficient()
destructor
void ATxPlusy(T a, MatrixType const &A, V const *x, T *y)
bool m_useInitialSol
whether use initial solutions or not
bool & m_useInitialSol
whether use initial solutions or not
void mapVariable2Constraint()
construct mapping from variables to constraints
model_type::variable_type variable_type
variable type
SubGradientDescent(value_type alpha=1, value_type beta=1)
constructor
coefficient_value_type m_bestObj
best objective found so far
Predicate whether a constraint is a capacity constraint.
SubGradientDescent(SubGradientDescent const &rhs)
copy constructor
V variable_value_type
V variable.
unsigned int numNegativeSlackConstraints(bool evaluateFlag)
get number of constraints with negative slackness in current iteration
value_type m_beta
constant
SolverProperty solveSubproblems(updater_type *updater, unsigned int beginIter, unsigned int endIter)
kernel lagrangian iterations
coefficient_value_type m_objConstant
constant value in objective from lagrangian relaxation
model_type::variable_type variable_type
variable type
void setLagObjFlag(bool f)
set evaluating objective of lagrangian subproblem in each iteration
std::vector< coefficient_value_type > const & m_vScalingFactor
scaling factor for constraints and objective, last entry is for objective
model_type::constraint_type constraint_type
constraint type
bool operator()(unsigned int i, unsigned int j) const
FeasibleSearcher< T, V > base_type
base type
T coefficient_value_type
T coefficient.
model_type::coefficient_value_type coefficient_value_type
coefficient value type
MultiKnapsackLagRelax & operator=(MultiKnapsackLagRelax const &rhs)
assignment
void copy(MultiKnapsackLagRelax const &rhs)
copy object
bool operator()(unsigned int id) const
solver_type::matrix_type matrix_type
matrix type
MinCoefficientScaler(value_type factor=1)
constructor
void computeMoveCost(constraint_type const &constr, std::vector< bool > const &vVariableProcess, std::vector< VariableMoveCost > &vVariableMoveCost) const
compute move cost for an item to move out from current bin
SolverProperty operator()(updater_type *updater=NULL, scaler_type *scaler=NULL, searcher_type *searcher=NULL)
API to run the algorithm.
expression_type const & objective() const
model_type::constraint_type constraint_type
constraint type
value_type operator()(constraint_type const &constr) const
API to compute scaling factor for constraints using L2 norm.
base_type::model_type model_type
model type
coefficient_value_type *& m_vSlackness
array of slackness values in each iteration,
coefficient_value_type m_lagObj
current objective of the lagrangian subproblem
std::vector< variable_value_type > m_vBestVariableSol
best feasible solution found so far
Describe linear constraint.
bool operator()(VariableMoveCost const &c1, VariableMoveCost const &c2) const
virtual SolverProperty operator()(updater_type *updater)
API to search for feasible solutions.
void bMinusAx(matrix_type const &A, VV const *x, TT const *b, TT *y) const
function to compute
virtual value_type operator()(constraint_type const &constr) const
API to compute scaling factor for constraints using L2 norm.
SubGradientDescent & operator=(SubGradientDescent const &rhs)
assignment
void printArray(unsigned int n, TT const *array, bool nonzeroFlag) const
print array
bool printLagMultiplier(std::string const &filename) const
print lagrangian multipliers to file
std::vector< constraint_type > const & constraints() const
bool operator()(variable_type const &v1, variable_type const &v2) const
numerical functions for linear algebra
model_type::variable_type variable_type
variable type
LinearModel< T, V > model_type
model type
unsigned int numVariables() const
base_type::solver_type solver_type
solver type
coefficient_value_type & m_objConstant
constant value in objective from lagrangian relaxation
base_type::model_type model_type
model type
void setMaxIterations(unsigned int maxIter)
set maximum iterations
base_type::expression_type expression_type
expression type
coefficient_value_type * m_vSlackness
array of slackness values in each iteration,
MultiKnapsackLagRelax< T, V > solver_type
solver type
MultiKnapsackLagRelax(model_type *model)
constructor
void axpy(unsigned int n, T a, V const *x, T *y)
Heuristic to search for feasible solutions by smoothing dense bins.
void mapVariable2Group()
construct mapping from variables to groups
CapacityConstraintPred(std::vector< constraint_type > const &v)
constructor
~SubGradientDescent()
destructor
base_type::value_type value_type
value type
unsigned int & m_maxIters
maximum number of iterations
Compare constraints by their slackness.
SearchByBinSmoothing< coefficient_value_type, variable_value_type > m_searcherSmoothing
search by smoothing dense bins
bool operator()(constraint_type const &constr) const
model_type::expression_type expression_type
expression type
CompareConstraintSlack(coefficient_value_type const *v)
constructor
model_type::term_type term_type
term type
std::ostream & printConstraint(std::ostream &os, std::string const &name) const
print constraint
std::vector< unsigned int > const & m_vConstraintPartition
indices of constraints, the first partition is capacity constraints
bool printObjCoef(std::string const &filename) const
print coefficients of variables in objective to file
Solve multiple knapsack problem with lagrangian relaxation.
coefficient_value_type & m_bestObj
best objective found so far
coefficient_value_type *& m_vObjCoef
coefficients variables in objective
model_type::expression_type expression_type
expression type
base_type::solver_type solver_type
solver type
void destroy()
destroy model
Base class for scaling scheme with default no scaling.
expression_type const & expression() const
coefficient_value_type evaluateLagObjective() const
evaluate objective of the lagrangian subproblem
#define limboStaticAssert(condition)
compile time assertion
LagMultiplierUpdater()
constructor
model_type::term_type term_type
term type
variable_type * m_vGroupedVariable
array of grouped variables according to item
model_type * m_model
model for the problem
~L2NormScaler()
destructor
SolverProperty solve(updater_type *updater, scaler_type *scaler, searcher_type *searcher)
kernel function to solve the problem
virtual SolverProperty operator()(updater_type *)
API to search for feasible solutions.
model_type::expression_type expression_type
expression type
SearchByAdjustCoefficient< coefficient_value_type, variable_value_type > m_searcherCoeff
search by adjusting coefficient
value_type operator()(expression_type const &expr) const
API to compute scaling factor for expression using L2 norm.
base_type::model_type model_type
model type
FeasibleSearcher< T, V > base_type
base type
coefficient_value_type * m_vObjCoef
coefficients variables in objective
L2NormScaler()
constructor
model_type::coefficient_value_type value_type
value type
void unscale()
recover problem from scaling
virtual ~LagMultiplierUpdater()
destructor
std::vector< coefficient_value_type > m_vScalingFactor
scaling factor for constraints and objective, last entry is for objective
value_type m_scalingFactor
constant scaling factor
solver_type::updater_type updater_type
updater type for lagrangian multipliers
coefficient_value_type & m_lagObj
current objective of the lagrangian subproblem
model_type::constraint_type constraint_type
constraint type
model_type::variable_type variable_type
variable type
matrix_type m_constrMatrix
constraint matrix
SearchByAdjustCoefficient(solver_type *solver, coefficient_value_type convergeRatio=0.1)
constructor
ProblemScaler()
constructor
Heuristic to search for feasible solutions by combined strategies.
Update lagrangian multiplier with subgradient descent.
std::iterator_traits< Iterator >::value_type max(Iterator first, Iterator last)
get max of an array
model_type::coefficient_value_type coefficient_value_type
coefficient value type
std::vector< variable_value_type > & m_vBestVariableSol
best feasible solution found so far
VariableMoveCost(variable_type var, variable_type targetVar, coefficient_value_type mc)
constructor
model_type::coefficient_value_type coefficient_value_type
coefficient value type
unsigned int m_iter
current iteration
coefficient_value_type rightHandSide() const
virtual SolverProperty operator()(updater_type *)
API to search for feasible solutions.
matrix_type const & m_constrMatrix
constraint matrix
base_type::constraint_type constraint_type
constraint type
coefficient_value_type moveCost
move cost
model_type::variable_value_type variable_value_type
variable value type
coefficient_value_type * m_vConstrRhs
constraint right hand side
LagMultiplierUpdater< T > base_type
base type
Compare variables by its move cost.
void vcopy(unsigned int n, T const *x, T *y)
copy vector
CompareVariableByCoefficient(coefficient_value_type const *v)
constructor
unsigned int * m_vVariableGroupBeginIndex
begin index of grouped variable
virtual ~FeasibleSearcher()
destructor
void scale(scaler_type *scaler)
scale problem for better numerical instability
model_type::term_type term_type
term type
model_type::expression_type expression_type
expression type
variable_type variable
variable of the item for the original bin
Scaling scheme with default L2 norm scaling.
void computeMoveCost(constraint_type const &constr, std::vector< VariableMoveCost > &vVariableMoveCost) const
compute move cost for an item to move out from current bin
solver_type * m_solver
problem solver
#define limboAssert(condition)
custom assertion without message
int limboPrint(MessageType m, const char *format,...)
formatted print with prefix
~SearchByBinSmoothing()
destructor
void computeSlackness()
compute slackness in an iteration
std::vector< term_type > const & terms() const
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 fe...
void operator()(unsigned int iter, unsigned int n, value_type const *vSlackness, value_type const *vLagMultiplier, value_type *vNewLagMultiplier)
API to update lagrangian multiplier using subgradient descent.
void AxPlusy(T a, MatrixType const &A, V const *x, T *y)
coefficient_value_type const * vObjCoef
coefficients in objective for comparison
model_type::constraint_type constraint_type
constraint type
solver_type::updater_type updater_type
updater type for lagrangian multipliers
void setUseInitialSolutions(bool f)
set whether use initial solutions
void updateLagMultipliers(updater_type *updater)
update lagrangian multipliers
unsigned int m_numGroups
number of groups
model_type::variable_value_type variable_value_type
variable value type
base_type::value_type value_type
value type
void computeScalingFactor(unsigned int iter)
compute scaling factor
Wrapper for the move cost of an item.
model_type::expression_type expression_type
expression type
value_type operator()(constraint_type const &constr) const
API to compute scaling factor for constraints using L2 norm.
base_type::solver_type solver_type
solver type
coefficient_value_type m_convergeRatio
ratio for convergence criteria, how much percent the number of negative slacks reduced ...
void setVariableSolution(variable_type const &var, variable_value_type v)
ProblemScaler< T, V > base_type
base type
SolverProperty converge()
check convergence of current solution
unsigned int const & m_numGroups
number of groups
model to describe an optimization problem
base_type::value_type value_type
value type
unsigned int & m_iter
current iteration
void copy(SubGradientDescent const &rhs)
copy object
index_type numRows
number of rows, not in the CSR format
virtual value_type operator()(unsigned int iter, value_type multiplier, value_type slackness)=0
API to update lagrangian multiplier.
void solveLag()
solve lagrangian subproblem
unsigned int maxIterations() const
variable_type *const & m_vGroupedVariable
array of grouped variables according to item
std::iterator_traits< Iterator >::value_type min(Iterator first, Iterator last)
get min of an array
base_type::expression_type expression_type
expression type
value_type m_scalingFactor
scaling factor
SearchByBinSmoothing(solver_type *solver)
constructor
void prepare()
prepare weights of variables in objective and classify constraints by marking capacity constraints an...
coefficient_value_type * m_vLagMultiplier
array of lagrangian multipliers
virtual SolverProperty operator()(updater_type *updater)
API to search for feasible solutions.
solver_type::matrix_type matrix_type
matrix type
solver_type::updater_type updater_type
updater type for lagrangian multipliers
A base helper function object to update lagrangian multipliers using subgradient descent. All other schemes can be derived from this class.
unsigned int m_iter
current iteration
VariableMoveCost(variable_type var, coefficient_value_type mc, coefficient_value_type cap)
constructor
Compare variables by its move cost.
std::vector< constraint_type > const & vConstraint
constraints
value_type operator()(unsigned int iter, value_type multiplier, value_type slackness)
API to update lagrangian multiplier using subgradient descent.
coefficient_value_type moveCost
move cost
Wrapper for the move cost of an item.
virtual ~ProblemScaler()
destructor
base_type::model_type model_type
model type
coefficient_value_type capacity
capacity of the item
std::vector< std::vector< std::pair< unsigned int, unsigned int > > > m_mVariable2Constr
map variables to constraints by pair of (constraint index, term index), a variable may have multiple ...
Heuristic to search for feasible solutions by adjusting coefficients so that some items will not be a...
coefficient_value_type * m_vNewLagMultiplier
array of new lagrangian multipliers, temporary storage
T dot(unsigned int n, T const *x, T const *y)
compute dot product
bool operator()(VariableMoveCost const &c1, VariableMoveCost const &c2) const
base_type::constraint_type constraint_type
constraint type