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	VariableMoveCost
	Wrapper for the move cost of an item. More...
struct	CompareVariableMoveCost
	Compare variables by its move cost. 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
	~SearchByAdjustCoefficient ()
	destructor
virtual SolverProperty	operator() (updater_type *updater)
	API to search for feasible solutions.
Public Member Functions inherited from limbo::solvers::FeasibleSearcher< T, V >
	FeasibleSearcher (solver_type *solver)
	constructor
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
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

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 1301 of file MultiKnapsackLagRelax.h.

Member Typedef Documentation

◆ base_type

template<typename T, typename V>

typedef FeasibleSearcher<T, V> limbo::solvers::SearchByAdjustCoefficient< T, V >::base_type

base type

Definition at line 1305 of file MultiKnapsackLagRelax.h.

◆ coefficient_value_type

template<typename T, typename V>

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

coefficient value type

Definition at line 1313 of file MultiKnapsackLagRelax.h.

◆ constraint_type

template<typename T, typename V>

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

constraint type

Definition at line 1321 of file MultiKnapsackLagRelax.h.

◆ expression_type

template<typename T, typename V>

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

expression type

Definition at line 1319 of file MultiKnapsackLagRelax.h.

◆ matrix_type

template<typename T, typename V>

typedef solver_type::matrix_type limbo::solvers::SearchByAdjustCoefficient< T, V >::matrix_type

matrix type

Definition at line 1325 of file MultiKnapsackLagRelax.h.

◆ model_type

template<typename T, typename V>

typedef base_type::model_type limbo::solvers::SearchByAdjustCoefficient< T, V >::model_type

model type

Definition at line 1307 of file MultiKnapsackLagRelax.h.

◆ solver_type

template<typename T, typename V>

typedef base_type::solver_type limbo::solvers::SearchByAdjustCoefficient< T, V >::solver_type

solver type

Definition at line 1309 of file MultiKnapsackLagRelax.h.

◆ term_type

template<typename T, typename V>

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

term type

Definition at line 1323 of file MultiKnapsackLagRelax.h.

◆ updater_type

template<typename T, typename V>

typedef solver_type::updater_type limbo::solvers::SearchByAdjustCoefficient< T, V >::updater_type

updater type for lagrangian multipliers

Definition at line 1311 of file MultiKnapsackLagRelax.h.

◆ variable_type

template<typename T, typename V>

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

variable type

Definition at line 1317 of file MultiKnapsackLagRelax.h.

◆ variable_value_type

template<typename T, typename V>

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

variable value type

Definition at line 1315 of file MultiKnapsackLagRelax.h.

Constructor & Destructor Documentation

◆ SearchByAdjustCoefficient()

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.

◆ ~SearchByAdjustCoefficient()

template<typename T, typename V>

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

inline

destructor

Definition at line 1363 of file MultiKnapsackLagRelax.h.

Member Function Documentation

◆ computeMoveCost()

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.

◆ mapVariable2Group()

template<typename T, typename V>

void limbo::solvers::SearchByAdjustCoefficient< T, V >::mapVariable2Group ( )

inlineprotected

construct mapping from variables to groups

Definition at line 1432 of file MultiKnapsackLagRelax.h.

◆ operator()()

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.

Member Data Documentation

◆ m_convergeRatio

template<typename T, typename V>

coefficient_value_type limbo::solvers::SearchByAdjustCoefficient< T, V >::m_convergeRatio

protected

ratio for convergence criteria, how much percent the number of negative slacks reduced

Definition at line 1480 of file MultiKnapsackLagRelax.h.

◆ m_vVariable2Group

template<typename T, typename V>

std::vector<unsigned int> limbo::solvers::SearchByAdjustCoefficient< T, V >::m_vVariable2Group

protected

map variables to groups

Definition at line 1479 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

Detailed Description

Member Typedef Documentation

◆ base_type

◆ coefficient_value_type

◆ constraint_type

◆ expression_type

◆ matrix_type

◆ model_type

◆ solver_type

◆ term_type

◆ updater_type

◆ variable_type

◆ variable_value_type

Constructor & Destructor Documentation

◆ SearchByAdjustCoefficient()

◆ ~SearchByAdjustCoefficient()

Member Function Documentation

◆ computeMoveCost()

◆ mapVariable2Group()

◆ operator()()

Member Data Documentation

◆ m_convergeRatio

◆ m_vVariable2Group