limbo::solvers::MultiKnapsackLagRelax< T, V > Class Template Reference

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 Parameters filename output file name Returns true if succeed
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 >

Detailed Description

template<typename T, typename V>
class limbo::solvers::MultiKnapsackLagRelax< T, V >

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.

Template Parameters

T	coefficient type
V	variable type

Definition at line 66 of file MultiKnapsackLagRelax.h.

Constructor & Destructor Documentation

template<typename T, typename V>

limbo::solvers::MultiKnapsackLagRelax< T, V >::MultiKnapsackLagRelax ( model_type *  model )

inline

constructor

Parameters

model

pointer to the model of problem

Definition at line 87 of file MultiKnapsackLagRelax.h.

template<typename T, typename V>

limbo::solvers::MultiKnapsackLagRelax< T, V >::MultiKnapsackLagRelax ( MultiKnapsackLagRelax< T, V > const &  rhs )

inline

copy constructor

Parameters

rhs	right hand side

Definition at line 119 of file MultiKnapsackLagRelax.h.

Member Function Documentation

template<typename T, typename V>

template<typename TT , typename VV >

void limbo::solvers::MultiKnapsackLagRelax< T, V >::bMinusAx ( matrix_type const &  A, VV const *  x, TT const *  b, TT *  y  ) const

protected

function to compute \(b-Ax\)

Template Parameters

TT	coefficient value type
VV	variable value type

Parameters

A	matrix
x	vector
b	vector
y	output vector

template<typename T , typename V >

SolverProperty limbo::solvers::MultiKnapsackLagRelax< T, V >::converge ( )

protected

check convergence of current solution

Returns

limbo::solvers::SolverProperty OPTIMAL if converged; limbo::solvers::SolverProperty SUBOPTIMAL if a feasible solution found

Definition at line 743 of file MultiKnapsackLagRelax.h.

template<typename T , typename V >

bool limbo::solvers::MultiKnapsackLagRelax< T, V >::lagObjFlag

(

)

const

Returns

flag of whether evaluating objective of lagrangian subproblem

Definition at line 352 of file MultiKnapsackLagRelax.h.

template<typename T , typename V >

unsigned int limbo::solvers::MultiKnapsackLagRelax< T, V >::maxIterations

(

)

const

Returns

maximum iterations

Definition at line 332 of file MultiKnapsackLagRelax.h.

template<typename T , typename V >

unsigned int limbo::solvers::MultiKnapsackLagRelax< T, V >::numNegativeSlackConstraints

(

bool

evaluateFlag

)

get number of constraints with negative slackness in current iteration

Parameters

evaluateFlag

if true, recompute slackness for each constraint

Definition at line 362 of file MultiKnapsackLagRelax.h.

template<typename T, typename V>

SolverProperty limbo::solvers::MultiKnapsackLagRelax< T, V >::operator() ( updater_type *  updater = NULL, scaler_type *  scaler = NULL, searcher_type *  searcher = NULL  )

inline

API to run the algorithm.

Parameters

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.

template<typename T, typename V>

MultiKnapsackLagRelax& limbo::solvers::MultiKnapsackLagRelax< T, V >::operator= ( MultiKnapsackLagRelax< T, V > const &  rhs )

inline

assignment

Parameters

rhs	right hand side

Definition at line 125 of file MultiKnapsackLagRelax.h.

template<typename T, typename V>

SolverProperty limbo::solvers::MultiKnapsackLagRelax< T, V >::postProcess ( updater_type *  updater, searcher_type *  searcher, SolverProperty  status  )

protected

post process solution if failed to converge to OPTIMAL after maximum iteration. It choose the best feasible solutions in store

Parameters

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.

template<typename T , typename V >

template<typename TT >

void limbo::solvers::MultiKnapsackLagRelax< T, V >::printArray	(	unsigned int	n,
		TT const *	array,
		bool	nonzeroFlag
	)		const

print array

Template Parameters

TT	array data type

Parameters

n	dimension
array	array
nonzeroFlag	whether only dump nonzero elements

Definition at line 905 of file MultiKnapsackLagRelax.h.

template<typename T , typename V >

std::ostream & limbo::solvers::MultiKnapsackLagRelax< T, V >::printConstraint	(	std::ostream &	os,
		std::string const &	name
	)		const

print constraint

Parameters

os	output stream
name	constraint name

Returns

output stream

Definition at line 889 of file MultiKnapsackLagRelax.h.

template<typename T , typename V >

bool limbo::solvers::MultiKnapsackLagRelax< T, V >::printLagMultiplier

(

std::string const &

filename

)

const

print lagrangian multipliers to file

Parameters

filename

output file name

Returns

true if succeed

Definition at line 866 of file MultiKnapsackLagRelax.h.

template<typename T , typename V >

std::ostream & limbo::solvers::MultiKnapsackLagRelax< T, V >::printLagMultiplier

(

std::ostream &

os = std::cout

)

const

print lagrangian multipliers

Parameters

os	output stream

Returns

output stream

Definition at line 879 of file MultiKnapsackLagRelax.h.

template<typename T , typename V >

bool limbo::solvers::MultiKnapsackLagRelax< T, V >::printObjCoef

(

std::string const &

filename

)

const

print coefficients of variables in objective to file

Parameters

filename

output file name

Returns

true if succeed

Definition at line 843 of file MultiKnapsackLagRelax.h.

template<typename T , typename V >

std::ostream & limbo::solvers::MultiKnapsackLagRelax< T, V >::printObjCoef

(

std::ostream &

os = std::cout

)

const

print coefficients of variables in objective

Parameters

os	output stream

Returns

output stream

Definition at line 856 of file MultiKnapsackLagRelax.h.

template<typename T , typename V >

std::ostream & limbo::solvers::MultiKnapsackLagRelax< T, V >::printVariableGroup

(

std::ostream &

os = std::cout

)

const

print variable groups

Parameters

os	output stream

Returns

output stream

Definition at line 824 of file MultiKnapsackLagRelax.h.

template<typename T, typename V>

void limbo::solvers::MultiKnapsackLagRelax< T, V >::scale ( scaler_type *  scaler )

protected

scale problem for better numerical instability

Parameters

scaler

an object to scale constraints and objective, use default scaler if NULL

Definition at line 536 of file MultiKnapsackLagRelax.h.

template<typename T , typename V >

void limbo::solvers::MultiKnapsackLagRelax< T, V >::setMaxIterations

(

unsigned int

maxIter

)

set maximum iterations

Parameters

maxIter

maximum iterations

Definition at line 337 of file MultiKnapsackLagRelax.h.

template<typename T , typename V >

void limbo::solvers::MultiKnapsackLagRelax< T, V >::setUseInitialSolutions

(

bool

f

)

set whether use initial solutions

Parameters

f

flag

Definition at line 347 of file MultiKnapsackLagRelax.h.

template<typename T, typename V>

SolverProperty limbo::solvers::MultiKnapsackLagRelax< T, V >::solve ( updater_type *  updater, scaler_type *  scaler, searcher_type *  searcher  )

protected

kernel function to solve the problem

Parameters

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.

template<typename T, typename V>

SolverProperty limbo::solvers::MultiKnapsackLagRelax< T, V >::solveSubproblems ( updater_type *  updater, unsigned int  beginIter, unsigned int  endIter  )

protected

kernel lagrangian iterations

Parameters

updater	an object to update lagrangian multipliers
beginIter	begin iteration number
endIter	end iteration number

Definition at line 509 of file MultiKnapsackLagRelax.h.

template<typename T, typename V>

void limbo::solvers::MultiKnapsackLagRelax< T, V >::updateLagMultipliers ( updater_type *  updater )

protected

update lagrangian multipliers

Parameters

updater

an object to update lagrangian multipliers

Definition at line 673 of file MultiKnapsackLagRelax.h.

template<typename T , typename V >

bool limbo::solvers::MultiKnapsackLagRelax< T, V >::useInitialSolutions

(

)

const

Returns

flag of whether use initial solutions

Definition at line 342 of file MultiKnapsackLagRelax.h.

---

The documentation for this class was generated from the following file:

• /Users/yibolin/Documents/Projects/Limbo/limbo/solvers/MultiKnapsackLagRelax.h