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

Heuristic to search for feasible solutions by adjusting coefficients so that some items will not be assigned to some bins. More...

#include <MultiKnapsackLagRelax.h>

Inheritance diagram for limbo::solvers::SearchByAdjustCoefficient< T, V >:

Classes
struct	CompareVariableMoveCost
	Compare variables by its move cost. More...
struct	VariableMoveCost
	Wrapper for the move cost of an item. More...

Public Types
typedef FeasibleSearcher< T, V >	base_type
	base type
typedef base_type::model_type	model_type
	model type
typedef base_type::solver_type	solver_type
	solver type
typedef solver_type::updater_type	updater_type
	updater type for lagrangian multipliers
typedef model_type::coefficient_value_type	coefficient_value_type
	coefficient value type
typedef model_type::variable_value_type	variable_value_type
	variable value type
typedef model_type::variable_type	variable_type
	variable type
typedef model_type::expression_type	expression_type
	expression type
typedef model_type::constraint_type	constraint_type
	constraint type
typedef model_type::term_type	term_type
	term type
typedef solver_type::matrix_type	matrix_type
	matrix type
Public Types inherited from limbo::solvers::FeasibleSearcher< T, V >
typedef LinearModel< T, V >	model_type
	model type
typedef MultiKnapsackLagRelax < T, V >	solver_type
	solver type
typedef solver_type::updater_type	updater_type
	updater type for lagrangian multipliers
typedef model_type::coefficient_value_type	coefficient_value_type
	coefficient value type
typedef model_type::variable_value_type	variable_value_type
	variable value type
typedef model_type::variable_type	variable_type
	variable type
typedef model_type::expression_type	expression_type
	expression type
typedef model_type::constraint_type	constraint_type
	constraint type
typedef model_type::term_type	term_type
	term type
typedef solver_type::matrix_type	matrix_type
	matrix type

Public Member Functions
	SearchByAdjustCoefficient (solver_type *solver, coefficient_value_type convergeRatio=0.1)
	constructor More...
	~SearchByAdjustCoefficient ()
	destructor
virtual SolverProperty	operator() (updater_type *updater)
	API to search for feasible solutions. More...
Public Member Functions inherited from limbo::solvers::FeasibleSearcher< T, V >
	FeasibleSearcher (solver_type *solver)
	constructor More...
virtual	~FeasibleSearcher ()
	destructor

Protected Member Functions
void	mapVariable2Group ()
	construct mapping from variables to groups
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 More...
Protected Member Functions inherited from limbo::solvers::FeasibleSearcher< T, V >
void	computeSlackness ()
	compute slackness in an iteration
SolverProperty	solveSubproblems (updater_type *updater, unsigned int beginIter, unsigned int endIter)
	kernel lagrangian iterations More...

Protected Attributes
std::vector< unsigned int >	m_vVariable2Group
	map variables to groups
coefficient_value_type	m_convergeRatio
	ratio for convergence criteria, how much percent the number of negative slacks reduced
Protected Attributes inherited from limbo::solvers::FeasibleSearcher< T, V >
solver_type *	m_solver
	problem solver
model_type *const &	m_model
	model for the problem
coefficient_value_type *&	m_vObjCoef
	coefficients variables in objective
matrix_type const &	m_constrMatrix
	constraint matrix \(A\)
coefficient_value_type *const &	m_vConstrRhs
	constraint right hand side \(b\)
variable_type *const &	m_vGroupedVariable
	array of grouped variables according to item
unsigned int *const &	m_vVariableGroupBeginIndex
	begin index of grouped variable
unsigned int const &	m_numGroups
	number of groups
std::vector< unsigned int > const &	m_vConstraintPartition
	indices of constraints, the first partition is capacity constraints
coefficient_value_type *&	m_vLagMultiplier
	array of lagrangian multipliers
coefficient_value_type *&	m_vSlackness
	array of slackness values in each iteration, \( b-Ax \)
std::vector < coefficient_value_type > const &	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
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

Detailed Description

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

Heuristic to search for feasible solutions by adjusting coefficients so that some items will not be assigned to some bins.

Template Parameters

T	coefficient value type
V	variable value type

Definition at line 33 of file MultiKnapsackLagRelax.h.

Constructor & Destructor Documentation

template<typename T, typename V>

limbo::solvers::SearchByAdjustCoefficient< T, V >::SearchByAdjustCoefficient ( solver_type *  solver, coefficient_value_type  convergeRatio = 0.1  )

inline

constructor

Parameters

solver	problem solver
convergeRatio	ratio of convergence ratio

Definition at line 1361 of file MultiKnapsackLagRelax.h.

Member Function Documentation

template<typename T, typename V>

void limbo::solvers::SearchByAdjustCoefficient< T, V >::computeMoveCost ( constraint_type const &  constr, std::vector< bool > const &  vVariableProcess, std::vector< VariableMoveCost > &  vVariableMoveCost  ) const

inlineprotected

compute move cost for an item to move out from current bin

Parameters

constr	constraint or bin
vVariableProcess	flags denoting whether variables are processed or not
vVariableMoveCost	array of move cost

Definition at line 1451 of file MultiKnapsackLagRelax.h.

template<typename T, typename V>

virtual SolverProperty limbo::solvers::SearchByAdjustCoefficient< T, V >::operator() ( updater_type *  updater )

inlinevirtual

API to search for feasible solutions.

Parameters

updater

updater for lagrangian multipliers

Returns

solving status

Reimplemented from limbo::solvers::FeasibleSearcher< T, V >.

Reimplemented in limbo::solvers::SearchByBinSmoothing< T, V >, and limbo::solvers::SearchByBinSmoothing< coefficient_value_type, variable_value_type >.

Definition at line 1368 of file MultiKnapsackLagRelax.h.

---

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

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