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
	MultiKnapsackLagRelax (MultiKnapsackLagRelax const &rhs)
	copy constructor
MultiKnapsackLagRelax &	operator= (MultiKnapsackLagRelax const &rhs)
	assignment
	~MultiKnapsackLagRelax ()
	destructor
SolverProperty	operator() (updater_type updater=NULL, scaler_type scaler=NULL, searcher_type *searcher=NULL)
	API to run the algorithm.
unsigned int	maxIterations () const
void	setMaxIterations (unsigned int maxIter)
	set maximum iterations
bool	useInitialSolutions () const
void	setUseInitialSolutions (bool f)
	set whether use initial solutions
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
print functions for debug
bool	printVariableGroup (std::string const &filename) const
	print variable groups to file
std::ostream &	printVariableGroup (std::ostream &os=std::cout) const
	print variable groups
bool	printObjCoef (std::string const &filename) const
	print coefficients of variables in objective to file
std::ostream &	printObjCoef (std::ostream &os=std::cout) const
	print coefficients of variables in objective
bool	printLagMultiplier (std::string const &filename) const
	print lagrangian multipliers to file
std::ostream &	printLagMultiplier (std::ostream &os=std::cout) const
	print lagrangian multipliers
std::ostream &	printConstraint (std::ostream &os, std::string const &name) const
	print constraint
template<typename TT>
void	printArray (unsigned int n, TT const *array, bool nonzeroFlag) const
	print array

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
SolverProperty	solveSubproblems (updater_type *updater, unsigned int beginIter, unsigned int endIter)
	kernel lagrangian iterations
void	scale (scaler_type *scaler)
	scale problem for better numerical instability
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
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
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
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\)

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.

Member Typedef Documentation

◆ coefficient_value_type

template<typename T, typename V>

typedef model_type::coefficient_value_type limbo::solvers::MultiKnapsackLagRelax< T, V >::coefficient_value_type

Definition at line 72 of file MultiKnapsackLagRelax.h.

◆ constraint_type

template<typename T, typename V>

typedef model_type::constraint_type limbo::solvers::MultiKnapsackLagRelax< T, V >::constraint_type

Definition at line 75 of file MultiKnapsackLagRelax.h.

◆ expression_type

template<typename T, typename V>

typedef model_type::expression_type limbo::solvers::MultiKnapsackLagRelax< T, V >::expression_type

Definition at line 76 of file MultiKnapsackLagRelax.h.

◆ matrix_type

template<typename T, typename V>

typedef MatrixCSR<coefficient_value_type, int, 1> limbo::solvers::MultiKnapsackLagRelax< T, V >::matrix_type

Definition at line 79 of file MultiKnapsackLagRelax.h.

◆ model_type

template<typename T, typename V>

typedef LinearModel<T, V> limbo::solvers::MultiKnapsackLagRelax< T, V >::model_type

linear model type for the problem

Definition at line 70 of file MultiKnapsackLagRelax.h.

◆ property_type

template<typename T, typename V>

typedef model_type::property_type limbo::solvers::MultiKnapsackLagRelax< T, V >::property_type

Definition at line 78 of file MultiKnapsackLagRelax.h.

◆ scaler_type

template<typename T, typename V>

typedef ProblemScaler<coefficient_value_type, variable_value_type> limbo::solvers::MultiKnapsackLagRelax< T, V >::scaler_type

Definition at line 81 of file MultiKnapsackLagRelax.h.

◆ searcher_type

template<typename T, typename V>

typedef FeasibleSearcher<coefficient_value_type, variable_value_type> limbo::solvers::MultiKnapsackLagRelax< T, V >::searcher_type

Definition at line 82 of file MultiKnapsackLagRelax.h.

◆ term_type

template<typename T, typename V>

typedef model_type::term_type limbo::solvers::MultiKnapsackLagRelax< T, V >::term_type

Definition at line 77 of file MultiKnapsackLagRelax.h.

◆ updater_type

template<typename T, typename V>

typedef LagMultiplierUpdater<coefficient_value_type> limbo::solvers::MultiKnapsackLagRelax< T, V >::updater_type

Definition at line 80 of file MultiKnapsackLagRelax.h.

◆ variable_type

template<typename T, typename V>

typedef model_type::variable_type limbo::solvers::MultiKnapsackLagRelax< T, V >::variable_type

Definition at line 74 of file MultiKnapsackLagRelax.h.

◆ variable_value_type

template<typename T, typename V>

typedef model_type::variable_value_type limbo::solvers::MultiKnapsackLagRelax< T, V >::variable_value_type

Definition at line 73 of file MultiKnapsackLagRelax.h.

Constructor & Destructor Documentation

◆ MultiKnapsackLagRelax() [1/2]

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.

◆ MultiKnapsackLagRelax() [2/2]

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.

◆ ~MultiKnapsackLagRelax()

template<typename T, typename V>

limbo::solvers::MultiKnapsackLagRelax< T, V >::~MultiKnapsackLagRelax ( )

inline

destructor

Definition at line 132 of file MultiKnapsackLagRelax.h.

Member Function Documentation

◆ bMinusAx()

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

◆ computeSlackness()

template<typename T, typename V>

void limbo::solvers::MultiKnapsackLagRelax< T, V >::computeSlackness ( )

protected

compute slackness in an iteration

Definition at line 728 of file MultiKnapsackLagRelax.h.

◆ converge()

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.

◆ copy()

template<typename T, typename V>

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

protected

copy object

Definition at line 372 of file MultiKnapsackLagRelax.h.

◆ destroy()

template<typename T, typename V>

void limbo::solvers::MultiKnapsackLagRelax< T, V >::destroy ( )

protected

destroy model

Definition at line 422 of file MultiKnapsackLagRelax.h.

◆ evaluateLagObjective()

template<typename T, typename V>

MultiKnapsackLagRelax< T, V >::coefficient_value_type limbo::solvers::MultiKnapsackLagRelax< T, V >::evaluateLagObjective ( ) const

protected

evaluate objective of the lagrangian subproblem

Definition at line 734 of file MultiKnapsackLagRelax.h.

◆ lagObjFlag()

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.

◆ maxIterations()

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.

◆ numNegativeSlackConstraints()

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.

◆ operator()()

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.

◆ operator=()

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.

◆ postProcess()

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.

◆ prepare()

template<typename T, typename V>

void limbo::solvers::MultiKnapsackLagRelax< T, V >::prepare ( )

protected

prepare weights of variables in objective and classify constraints by marking capacity constraints and single item constraints

Definition at line 560 of file MultiKnapsackLagRelax.h.

◆ printArray()

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.

◆ printConstraint()

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.

◆ printLagMultiplier() [1/2]

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.

◆ printLagMultiplier() [2/2]

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.

◆ printObjCoef() [1/2]

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.

◆ printObjCoef() [2/2]

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.

◆ printVariableGroup() [1/2]

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.

◆ printVariableGroup() [2/2]

template<typename T, typename V>

bool limbo::solvers::MultiKnapsackLagRelax< T, V >::printVariableGroup ( std::string const & filename ) const

print variable groups to file

Parameters

filename output file name

Returns: true if succeed

Definition at line 811 of file MultiKnapsackLagRelax.h.

◆ scale()

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.

◆ setLagObjFlag()

template<typename T, typename V>

void limbo::solvers::MultiKnapsackLagRelax< T, V >::setLagObjFlag ( bool f )

set evaluating objective of lagrangian subproblem in each iteration

Definition at line 357 of file MultiKnapsackLagRelax.h.

◆ setMaxIterations()

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.

◆ setUseInitialSolutions()

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.

◆ solve()

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.

◆ solveLag()

template<typename T, typename V>

void limbo::solvers::MultiKnapsackLagRelax< T, V >::solveLag ( )

protected

solve lagrangian subproblem

Definition at line 702 of file MultiKnapsackLagRelax.h.

◆ solveSubproblems()

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.

◆ unscale()

template<typename T, typename V>

void limbo::solvers::MultiKnapsackLagRelax< T, V >::unscale ( )

protected

recover problem from scaling

Definition at line 551 of file MultiKnapsackLagRelax.h.

◆ updateLagMultipliers()

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.

◆ useInitialSolutions()

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.

◆ FeasibleSearcher< coefficient_value_type, variable_value_type >

template<typename T, typename V>

friend class FeasibleSearcher< coefficient_value_type, variable_value_type >

friend

Definition at line 325 of file MultiKnapsackLagRelax.h.

Member Data Documentation

◆ m_bestObj

template<typename T, typename V>

coefficient_value_type limbo::solvers::MultiKnapsackLagRelax< T, V >::m_bestObj

protected

best objective found so far

Definition at line 325 of file MultiKnapsackLagRelax.h.

◆ m_constrMatrix

template<typename T, typename V>

matrix_type limbo::solvers::MultiKnapsackLagRelax< T, V >::m_constrMatrix

protected

constraint matrix \(A\)

Definition at line 304 of file MultiKnapsackLagRelax.h.

◆ m_iter

template<typename T, typename V>

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

protected

current iteration

Definition at line 320 of file MultiKnapsackLagRelax.h.

◆ m_lagObj

template<typename T, typename V>

coefficient_value_type limbo::solvers::MultiKnapsackLagRelax< T, V >::m_lagObj

protected

current objective of the lagrangian subproblem

Definition at line 317 of file MultiKnapsackLagRelax.h.

◆ m_lagObjFlag

template<typename T, typename V>

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

protected

whether evaluate objective of the lagrangian subproblem in each iteration

Definition at line 318 of file MultiKnapsackLagRelax.h.

◆ m_maxIters

template<typename T, typename V>

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

protected

maximum number of iterations

Definition at line 321 of file MultiKnapsackLagRelax.h.

◆ m_model

template<typename T, typename V>

model_type* limbo::solvers::MultiKnapsackLagRelax< T, V >::m_model

protected

model for the problem

Definition at line 301 of file MultiKnapsackLagRelax.h.

◆ m_numGroups

template<typename T, typename V>

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

protected

number of groups

Definition at line 309 of file MultiKnapsackLagRelax.h.

◆ m_objConstant

template<typename T, typename V>

coefficient_value_type limbo::solvers::MultiKnapsackLagRelax< T, V >::m_objConstant

protected

constant value in objective from lagrangian relaxation

Definition at line 316 of file MultiKnapsackLagRelax.h.

◆ m_useInitialSol

template<typename T, typename V>

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

protected

whether use initial solutions or not

Definition at line 322 of file MultiKnapsackLagRelax.h.

◆ m_vBestVariableSol

template<typename T, typename V>

std::vector<variable_value_type> limbo::solvers::MultiKnapsackLagRelax< T, V >::m_vBestVariableSol

protected

best feasible solution found so far

Definition at line 324 of file MultiKnapsackLagRelax.h.

◆ m_vConstraintPartition

template<typename T, typename V>

std::vector<unsigned int> limbo::solvers::MultiKnapsackLagRelax< T, V >::m_vConstraintPartition

protected

indices of constraints, the first partition is capacity constraints

Definition at line 310 of file MultiKnapsackLagRelax.h.

◆ m_vConstrRhs

template<typename T, typename V>

coefficient_value_type* limbo::solvers::MultiKnapsackLagRelax< T, V >::m_vConstrRhs

protected

constraint right hand side \(b\)

Definition at line 305 of file MultiKnapsackLagRelax.h.

◆ m_vGroupedVariable

template<typename T, typename V>

variable_type* limbo::solvers::MultiKnapsackLagRelax< T, V >::m_vGroupedVariable

protected

array of grouped variables according to item

Definition at line 307 of file MultiKnapsackLagRelax.h.

◆ m_vLagMultiplier

template<typename T, typename V>

coefficient_value_type* limbo::solvers::MultiKnapsackLagRelax< T, V >::m_vLagMultiplier

protected

array of lagrangian multipliers

Definition at line 311 of file MultiKnapsackLagRelax.h.

◆ m_vNewLagMultiplier

template<typename T, typename V>

coefficient_value_type* limbo::solvers::MultiKnapsackLagRelax< T, V >::m_vNewLagMultiplier

protected

array of new lagrangian multipliers, temporary storage

Definition at line 312 of file MultiKnapsackLagRelax.h.

◆ m_vObjCoef

template<typename T, typename V>

coefficient_value_type* limbo::solvers::MultiKnapsackLagRelax< T, V >::m_vObjCoef

protected

coefficients variables in objective

Definition at line 303 of file MultiKnapsackLagRelax.h.

◆ m_vScalingFactor

template<typename T, typename V>

std::vector<coefficient_value_type> limbo::solvers::MultiKnapsackLagRelax< T, V >::m_vScalingFactor

protected

scaling factor for constraints and objective, last entry is for objective

Definition at line 314 of file MultiKnapsackLagRelax.h.

◆ m_vSlackness

template<typename T, typename V>

coefficient_value_type* limbo::solvers::MultiKnapsackLagRelax< T, V >::m_vSlackness

protected

array of slackness values in each iteration, \( b-Ax \)

Definition at line 313 of file MultiKnapsackLagRelax.h.

◆ m_vVariableGroupBeginIndex

template<typename T, typename V>

unsigned int* limbo::solvers::MultiKnapsackLagRelax< T, V >::m_vVariableGroupBeginIndex

protected

begin index of grouped variable

Definition at line 308 of file MultiKnapsackLagRelax.h.

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

/home/abuild/rpmbuild/BUILD/limbo-3.5.4-build/limbo-3.5.4/limbo/solvers/MultiKnapsackLagRelax.h

Classes

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ coefficient_value_type

◆ constraint_type

◆ expression_type

◆ matrix_type

◆ model_type

◆ property_type

◆ scaler_type

◆ searcher_type

◆ term_type

◆ updater_type

◆ variable_type

◆ variable_value_type

Constructor & Destructor Documentation

◆ MultiKnapsackLagRelax() [1/2]

◆ MultiKnapsackLagRelax() [2/2]

◆ ~MultiKnapsackLagRelax()

Member Function Documentation

◆ bMinusAx()

◆ computeSlackness()

◆ converge()

◆ copy()

◆ destroy()

◆ evaluateLagObjective()

◆ lagObjFlag()

◆ maxIterations()

◆ numNegativeSlackConstraints()

◆ operator()()

◆ operator=()

◆ postProcess()

◆ prepare()

◆ printArray()

◆ printConstraint()

◆ printLagMultiplier() [1/2]

◆ printLagMultiplier() [2/2]

◆ printObjCoef() [1/2]

◆ printObjCoef() [2/2]

◆ printVariableGroup() [1/2]

◆ printVariableGroup() [2/2]

◆ scale()

◆ setLagObjFlag()

◆ setMaxIterations()

◆ setUseInitialSolutions()

◆ solve()

◆ solveLag()

◆ solveSubproblems()

◆ unscale()

◆ updateLagMultipliers()

◆ useInitialSolutions()

Friends And Related Symbol Documentation

◆ FeasibleSearcher< coefficient_value_type, variable_value_type >

Member Data Documentation

◆ m_bestObj

◆ m_constrMatrix

◆ m_iter

◆ m_lagObj

◆ m_lagObjFlag

◆ m_maxIters

◆ m_model

◆ m_numGroups

◆ m_objConstant

◆ m_useInitialSol

◆ m_vBestVariableSol

◆ m_vConstraintPartition

◆ m_vConstrRhs

◆ m_vGroupedVariable

◆ m_vLagMultiplier

◆ m_vNewLagMultiplier

◆ m_vObjCoef

◆ m_vScalingFactor

◆ m_vSlackness

◆ m_vVariableGroupBeginIndex