Heuristic to search for feasible solutions by smoothing dense bins. More...

#include <MultiKnapsackLagRelax.h>

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

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

Public Types
typedef SearchByAdjustCoefficient< 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_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::SearchByAdjustCoefficient< T, V >
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
	SearchByBinSmoothing (solver_type *solver)
	constructor
	~SearchByBinSmoothing ()
	destructor
virtual SolverProperty	operator() (updater_type *)
	API to search for feasible solutions.
Public Member Functions inherited from limbo::solvers::SearchByAdjustCoefficient< T, V >
	SearchByAdjustCoefficient (solver_type *solver, coefficient_value_type convergeRatio=0.1)
	constructor
	~SearchByAdjustCoefficient ()
	destructor
Public Member Functions inherited from limbo::solvers::FeasibleSearcher< T, V >
	FeasibleSearcher (solver_type *solver)
	constructor
virtual	~FeasibleSearcher ()
	destructor

Protected Member Functions
void	mapVariable2Constraint ()
	construct mapping from variables to constraints
void	computeMoveCost (constraint_type const &constr, std::vector< VariableMoveCost > &vVariableMoveCost) const
	compute move cost for an item to move out from current bin
Protected Member Functions inherited from limbo::solvers::SearchByAdjustCoefficient< T, V >
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< 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 constraints
std::vector< coefficient_value_type >	m_vObjCoefOrig
	original coefficient of variable in objective
Protected Attributes inherited from limbo::solvers::SearchByAdjustCoefficient< T, V >
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::SearchByBinSmoothing< T, V >

Heuristic to search for feasible solutions by smoothing dense bins.

Template Parameters

T	coefficient value type
V	variable value type

Definition at line 1487 of file MultiKnapsackLagRelax.h.

Member Typedef Documentation

◆ base_type

template<typename T, typename V>

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

base type

Definition at line 1491 of file MultiKnapsackLagRelax.h.

◆ coefficient_value_type

template<typename T, typename V>

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

coefficient value type

Definition at line 1499 of file MultiKnapsackLagRelax.h.

◆ constraint_type

template<typename T, typename V>

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

constraint type

Definition at line 1505 of file MultiKnapsackLagRelax.h.

◆ expression_type

template<typename T, typename V>

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

expression type

Definition at line 1503 of file MultiKnapsackLagRelax.h.

◆ matrix_type

template<typename T, typename V>

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

matrix type

Definition at line 1509 of file MultiKnapsackLagRelax.h.

◆ model_type

template<typename T, typename V>

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

model type

Definition at line 1493 of file MultiKnapsackLagRelax.h.

◆ solver_type

template<typename T, typename V>

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

solver type

Definition at line 1495 of file MultiKnapsackLagRelax.h.

◆ term_type

template<typename T, typename V>

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

term type

Definition at line 1507 of file MultiKnapsackLagRelax.h.

◆ updater_type

template<typename T, typename V>

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

updater type for lagrangian multipliers

Definition at line 1497 of file MultiKnapsackLagRelax.h.

◆ variable_type

template<typename T, typename V>

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

variable type

Definition at line 1501 of file MultiKnapsackLagRelax.h.

Constructor & Destructor Documentation

◆ SearchByBinSmoothing()

template<typename T, typename V>

limbo::solvers::SearchByBinSmoothing< T, V >::SearchByBinSmoothing ( solver_type * solver )

inline

constructor

Parameters

solver problem solver

Definition at line 1562 of file MultiKnapsackLagRelax.h.

◆ ~SearchByBinSmoothing()

template<typename T, typename V>

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

inline

destructor

Definition at line 1564 of file MultiKnapsackLagRelax.h.

Member Function Documentation

◆ computeMoveCost()

template<typename T, typename V>

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

inlineprotected

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

Parameters

constr	constraint or bin
vVariableMoveCost	array of move cost

Definition at line 1668 of file MultiKnapsackLagRelax.h.

◆ mapVariable2Constraint()

template<typename T, typename V>

void limbo::solvers::SearchByBinSmoothing< T, V >::mapVariable2Constraint ( )

inlineprotected

construct mapping from variables to constraints

Definition at line 1650 of file MultiKnapsackLagRelax.h.

◆ operator()()

template<typename T, typename V>

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

inlinevirtual

API to search for feasible solutions.

param updater updater for lagrangian multipliers

Returns: solving status

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

Definition at line 1570 of file MultiKnapsackLagRelax.h.

Member Data Documentation

◆ m_mVariable2Constr

template<typename T, typename V>

std::vector<std::vector<std::pair<unsigned int, unsigned int> > > limbo::solvers::SearchByBinSmoothing< T, V >::m_mVariable2Constr

protected

map variables to constraints by pair of (constraint index, term index), a variable may have multiple constraints

Definition at line 1717 of file MultiKnapsackLagRelax.h.

◆ m_vObjCoefOrig

template<typename T, typename V>

std::vector<coefficient_value_type> limbo::solvers::SearchByBinSmoothing< T, V >::m_vObjCoefOrig

protected

original coefficient of variable in objective

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

Constructor & Destructor Documentation

◆ SearchByBinSmoothing()

◆ ~SearchByBinSmoothing()

Member Function Documentation

◆ computeMoveCost()

◆ mapVariable2Constraint()

◆ operator()()

Member Data Documentation

◆ m_mVariable2Constr

◆ m_vObjCoefOrig