Base heuristic to search for feasible solutions. More...

#include <MultiKnapsackLagRelax.h>

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

Public Types
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
	FeasibleSearcher (solver_type *solver)
	constructor
virtual	~FeasibleSearcher ()
	destructor
virtual SolverProperty	operator() (updater_type *)
	API to search for feasible solutions.

Protected Member Functions
void	computeSlackness ()
	compute slackness in an iteration
SolverProperty	solveSubproblems (updater_type *updater, unsigned int beginIter, unsigned int endIter)
	kernel lagrangian iterations

Protected Attributes
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::FeasibleSearcher< T, V >

Base heuristic to search for feasible solutions.

Template Parameters

T	coefficient value type
V	variable value type

Definition at line 1200 of file MultiKnapsackLagRelax.h.

Member Typedef Documentation

◆ coefficient_value_type

template<typename T, typename V>

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

coefficient value type

Definition at line 1210 of file MultiKnapsackLagRelax.h.

◆ constraint_type

template<typename T, typename V>

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

constraint type

Definition at line 1218 of file MultiKnapsackLagRelax.h.

◆ expression_type

template<typename T, typename V>

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

expression type

Definition at line 1216 of file MultiKnapsackLagRelax.h.

◆ matrix_type

template<typename T, typename V>

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

matrix type

Definition at line 1222 of file MultiKnapsackLagRelax.h.

◆ model_type

template<typename T, typename V>

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

model type

Definition at line 1204 of file MultiKnapsackLagRelax.h.

◆ solver_type

template<typename T, typename V>

typedef MultiKnapsackLagRelax<T, V> limbo::solvers::FeasibleSearcher< T, V >::solver_type

solver type

Definition at line 1206 of file MultiKnapsackLagRelax.h.

◆ term_type

template<typename T, typename V>

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

term type

Definition at line 1220 of file MultiKnapsackLagRelax.h.

◆ updater_type

template<typename T, typename V>

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

updater type for lagrangian multipliers

Definition at line 1208 of file MultiKnapsackLagRelax.h.

◆ variable_type

template<typename T, typename V>

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

variable type

Definition at line 1214 of file MultiKnapsackLagRelax.h.

◆ variable_value_type

template<typename T, typename V>

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

variable value type

Definition at line 1212 of file MultiKnapsackLagRelax.h.

Constructor & Destructor Documentation

◆ FeasibleSearcher()

template<typename T, typename V>

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

inline

constructor

Parameters

solver problem solver

Definition at line 1226 of file MultiKnapsackLagRelax.h.

◆ ~FeasibleSearcher()

template<typename T, typename V>

virtual limbo::solvers::FeasibleSearcher< T, V >::~FeasibleSearcher ( )

inlinevirtual

destructor

Definition at line 1249 of file MultiKnapsackLagRelax.h.

Member Function Documentation

◆ computeSlackness()

template<typename T, typename V>

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

inlineprotected

compute slackness in an iteration

Definition at line 1259 of file MultiKnapsackLagRelax.h.

◆ operator()()

template<typename T, typename V>

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

inlinevirtual

API to search for feasible solutions.

param updater updater for lagrangian multipliers

Returns: solving status

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

Definition at line 1255 of file MultiKnapsackLagRelax.h.

◆ solveSubproblems()

template<typename T, typename V>

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

inlineprotected

kernel lagrangian iterations

Parameters

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

Definition at line 1267 of file MultiKnapsackLagRelax.h.

Member Data Documentation

◆ m_bestObj

template<typename T, typename V>

coefficient_value_type& limbo::solvers::FeasibleSearcher< T, V >::m_bestObj

protected

best objective found so far

Definition at line 1293 of file MultiKnapsackLagRelax.h.

◆ m_constrMatrix

template<typename T, typename V>

matrix_type const& limbo::solvers::FeasibleSearcher< T, V >::m_constrMatrix

protected

constraint matrix \(A\)

Definition at line 1276 of file MultiKnapsackLagRelax.h.

◆ m_iter

template<typename T, typename V>

unsigned int& limbo::solvers::FeasibleSearcher< T, V >::m_iter

protected

current iteration

Definition at line 1288 of file MultiKnapsackLagRelax.h.

◆ m_lagObj

template<typename T, typename V>

coefficient_value_type& limbo::solvers::FeasibleSearcher< T, V >::m_lagObj

protected

current objective of the lagrangian subproblem

Definition at line 1287 of file MultiKnapsackLagRelax.h.

◆ m_maxIters

template<typename T, typename V>

unsigned int& limbo::solvers::FeasibleSearcher< T, V >::m_maxIters

protected

maximum number of iterations

Definition at line 1289 of file MultiKnapsackLagRelax.h.

◆ m_model

template<typename T, typename V>

model_type* const& limbo::solvers::FeasibleSearcher< T, V >::m_model

protected

model for the problem

Definition at line 1273 of file MultiKnapsackLagRelax.h.

◆ m_numGroups

template<typename T, typename V>

unsigned int const& limbo::solvers::FeasibleSearcher< T, V >::m_numGroups

protected

number of groups

Definition at line 1281 of file MultiKnapsackLagRelax.h.

◆ m_objConstant

template<typename T, typename V>

coefficient_value_type& limbo::solvers::FeasibleSearcher< T, V >::m_objConstant

protected

constant value in objective from lagrangian relaxation

Definition at line 1286 of file MultiKnapsackLagRelax.h.

◆ m_solver

template<typename T, typename V>

solver_type* limbo::solvers::FeasibleSearcher< T, V >::m_solver

protected

problem solver

Definition at line 1272 of file MultiKnapsackLagRelax.h.

◆ m_useInitialSol

template<typename T, typename V>

bool& limbo::solvers::FeasibleSearcher< T, V >::m_useInitialSol

protected

whether use initial solutions or not

Definition at line 1290 of file MultiKnapsackLagRelax.h.

◆ m_vBestVariableSol

template<typename T, typename V>

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

protected

best feasible solution found so far

Definition at line 1292 of file MultiKnapsackLagRelax.h.

◆ m_vConstraintPartition

template<typename T, typename V>

std::vector<unsigned int> const& limbo::solvers::FeasibleSearcher< T, V >::m_vConstraintPartition

protected

indices of constraints, the first partition is capacity constraints

Definition at line 1282 of file MultiKnapsackLagRelax.h.

◆ m_vConstrRhs

template<typename T, typename V>

coefficient_value_type* const& limbo::solvers::FeasibleSearcher< T, V >::m_vConstrRhs

protected

constraint right hand side \(b\)

Definition at line 1277 of file MultiKnapsackLagRelax.h.

◆ m_vGroupedVariable

template<typename T, typename V>

variable_type* const& limbo::solvers::FeasibleSearcher< T, V >::m_vGroupedVariable

protected

array of grouped variables according to item

Definition at line 1279 of file MultiKnapsackLagRelax.h.

◆ m_vLagMultiplier

template<typename T, typename V>

coefficient_value_type*& limbo::solvers::FeasibleSearcher< T, V >::m_vLagMultiplier

protected

array of lagrangian multipliers

Definition at line 1283 of file MultiKnapsackLagRelax.h.

◆ m_vObjCoef

template<typename T, typename V>

coefficient_value_type*& limbo::solvers::FeasibleSearcher< T, V >::m_vObjCoef

protected

coefficients variables in objective

Definition at line 1275 of file MultiKnapsackLagRelax.h.

◆ m_vScalingFactor

template<typename T, typename V>

std::vector<coefficient_value_type> const& limbo::solvers::FeasibleSearcher< T, V >::m_vScalingFactor

protected

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

Definition at line 1285 of file MultiKnapsackLagRelax.h.

◆ m_vSlackness

template<typename T, typename V>

coefficient_value_type*& limbo::solvers::FeasibleSearcher< T, V >::m_vSlackness

protected

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

Definition at line 1284 of file MultiKnapsackLagRelax.h.

◆ m_vVariableGroupBeginIndex

template<typename T, typename V>

unsigned int* const& limbo::solvers::FeasibleSearcher< T, V >::m_vVariableGroupBeginIndex

protected

begin index of grouped variable

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

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ 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

◆ FeasibleSearcher()

◆ ~FeasibleSearcher()

Member Function Documentation

◆ computeSlackness()

◆ operator()()

◆ solveSubproblems()

Member Data Documentation

◆ m_bestObj

◆ m_constrMatrix

◆ m_iter

◆ m_lagObj

◆ m_maxIters

◆ m_model

◆ m_numGroups

◆ m_objConstant

◆ m_solver

◆ m_useInitialSol

◆ m_vBestVariableSol

◆ m_vConstraintPartition

◆ m_vConstrRhs

◆ m_vGroupedVariable

◆ m_vLagMultiplier

◆ m_vObjCoef

◆ m_vScalingFactor

◆ m_vSlackness

◆ m_vVariableGroupBeginIndex