LP solved with min-cost flow. More...

#include <MinCostFlow.h>

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 variable_value_type	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 lemon::SmartDigraph	graph_type
typedef graph_type::Node	node_type
typedef graph_type::Arc	arc_type
typedef graph_type::NodeMap< value_type >	node_value_map_type
typedef graph_type::NodeMap< std::string >	node_name_map_type
typedef graph_type::ArcMap< std::string >	arc_name_map_type
typedef graph_type::ArcMap< value_type >	arc_value_map_type
typedef graph_type::ArcMap< value_type >	arc_cost_map_type
typedef graph_type::ArcMap< value_type >	arc_flow_map_type
typedef graph_type::NodeMap< value_type >	node_pot_map_type
typedef MinCostFlowSolver< coefficient_value_type, variable_value_type >	solver_type

Public Member Functions
	MinCostFlow (model_type *model)
	constructor
	~MinCostFlow ()
	destructor
SolverProperty	operator() (solver_type *solver=NULL)
	API to run the algorithm.
graph_type const &	graph () const
arc_value_map_type const &	lowerMap () const
arc_value_map_type const &	upperMap () const
arc_cost_map_type const &	costMap () const
node_value_map_type const &	supplyMap () const
arc_flow_map_type &	flowMap ()
node_pot_map_type &	potentialMap ()
value_type	totalFlowCost () const
void	setTotalFlowCost (value_type cost)
value_type	totalCost () const
print functions to debug.lgf
void	printGraph (bool writeSol) const
	print graph

Protected Member Functions
	MinCostFlow (MinCostFlow const &rhs)
	copy constructor, forbidden
MinCostFlow &	operator= (MinCostFlow const &rhs)
	assignment, forbidden
SolverProperty	solve (solver_type *solver)
	kernel function to solve the problem
void	buildGraph ()
	build min-cost flow graph
void	setObjective (expression_type const &obj)
	set objective, support incremental set
void	applySolution ()
	apply solutions to model

Protected Attributes
model_type *	m_model
	model for the problem
graph_type	m_graph
	input graph
arc_value_map_type	m_mLower
	lower bound of flow, usually zero
arc_value_map_type	m_mUpper
	upper bound of flow, arc capacity in min-cost flow
arc_cost_map_type	m_mCost
	arc cost in min-cost flow
node_value_map_type	m_mSupply
	node supply in min-cost flow
value_type	m_totalFlowCost
	total cost after solving
arc_flow_map_type	m_mFlow
	solution of min-cost flow, which is the solution of LP
node_pot_map_type	m_mPotential
	solution of min-cost flow, which is the dual solution of LP

Detailed Description

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

LP solved with min-cost flow.

The primal problem of this LP is a min-cost flow problem, so we can solve the graph problem.

Primal problem

\begin{eqnarray*}& min. & \sum_{i, j \in E} c_{ij} \cdot x_{ij}, \\ & s.t. & l_{ij} \le x_{ij} \le u_{ij}, \forall (i, j) \in E, \\ & & \sum_{j \in V} x_{ij} = s_i, \forall i \ne t, \in V, \\ & & x_{ij} = -x_{ji}, \forall (i, j) \in E. (implicit) \end{eqnarray*}

Only CapacityScaling algorithm supports real-value costs. All other algorithms require integer costs, supply and capacity.

Template Parameters

T	coefficient type
V	variable type

Definition at line 60 of file MinCostFlow.h.

Member Typedef Documentation

◆ arc_cost_map_type

template<typename T, typename V>

typedef graph_type::ArcMap<value_type> limbo::solvers::MinCostFlow< T, V >::arc_cost_map_type

Definition at line 82 of file MinCostFlow.h.

◆ arc_flow_map_type

template<typename T, typename V>

typedef graph_type::ArcMap<value_type> limbo::solvers::MinCostFlow< T, V >::arc_flow_map_type

Definition at line 83 of file MinCostFlow.h.

◆ arc_name_map_type

template<typename T, typename V>

typedef graph_type::ArcMap<std::string> limbo::solvers::MinCostFlow< T, V >::arc_name_map_type

Definition at line 80 of file MinCostFlow.h.

◆ arc_type

template<typename T, typename V>

typedef graph_type::Arc limbo::solvers::MinCostFlow< T, V >::arc_type

Definition at line 77 of file MinCostFlow.h.

◆ arc_value_map_type

template<typename T, typename V>

typedef graph_type::ArcMap<value_type> limbo::solvers::MinCostFlow< T, V >::arc_value_map_type

Definition at line 81 of file MinCostFlow.h.

◆ coefficient_value_type

template<typename T, typename V>

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

Definition at line 66 of file MinCostFlow.h.

◆ constraint_type

template<typename T, typename V>

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

Definition at line 70 of file MinCostFlow.h.

◆ expression_type

template<typename T, typename V>

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

Definition at line 71 of file MinCostFlow.h.

◆ graph_type

template<typename T, typename V>

typedef lemon::SmartDigraph limbo::solvers::MinCostFlow< T, V >::graph_type

Definition at line 75 of file MinCostFlow.h.

◆ model_type

template<typename T, typename V>

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

linear model type for the problem

Definition at line 64 of file MinCostFlow.h.

◆ node_name_map_type

template<typename T, typename V>

typedef graph_type::NodeMap<std::string> limbo::solvers::MinCostFlow< T, V >::node_name_map_type

Definition at line 79 of file MinCostFlow.h.

◆ node_pot_map_type

template<typename T, typename V>

typedef graph_type::NodeMap<value_type> limbo::solvers::MinCostFlow< T, V >::node_pot_map_type

Definition at line 84 of file MinCostFlow.h.

◆ node_type

template<typename T, typename V>

typedef graph_type::Node limbo::solvers::MinCostFlow< T, V >::node_type

Definition at line 76 of file MinCostFlow.h.

◆ node_value_map_type

template<typename T, typename V>

typedef graph_type::NodeMap<value_type> limbo::solvers::MinCostFlow< T, V >::node_value_map_type

Definition at line 78 of file MinCostFlow.h.

◆ property_type

template<typename T, typename V>

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

Definition at line 73 of file MinCostFlow.h.

◆ solver_type

template<typename T, typename V>

typedef MinCostFlowSolver<coefficient_value_type, variable_value_type> limbo::solvers::MinCostFlow< T, V >::solver_type

Definition at line 86 of file MinCostFlow.h.

◆ term_type

template<typename T, typename V>

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

Definition at line 72 of file MinCostFlow.h.

◆ value_type

template<typename T, typename V>

typedef variable_value_type limbo::solvers::MinCostFlow< T, V >::value_type

Definition at line 68 of file MinCostFlow.h.

◆ variable_type

template<typename T, typename V>

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

Definition at line 69 of file MinCostFlow.h.

◆ variable_value_type

template<typename T, typename V>

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

Definition at line 67 of file MinCostFlow.h.

Constructor & Destructor Documentation

◆ MinCostFlow() [1/2]

template<typename T, typename V>

limbo::solvers::MinCostFlow< T, V >::MinCostFlow ( model_type * model )

inline

constructor

Parameters

model pointer to the model of problem

Definition at line 91 of file MinCostFlow.h.

◆ ~MinCostFlow()

template<typename T, typename V>

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

inline

destructor

Definition at line 104 of file MinCostFlow.h.

◆ MinCostFlow() [2/2]

template<typename T, typename V>

limbo::solvers::MinCostFlow< T, V >::MinCostFlow ( MinCostFlow< T, V > const & rhs )

protected

copy constructor, forbidden

Parameters

rhs	right hand side

Member Function Documentation

◆ applySolution()

template<typename T, typename V>

void limbo::solvers::MinCostFlow< T, V >::applySolution ( )

protected

apply solutions to model

Definition at line 446 of file MinCostFlow.h.

◆ buildGraph()

template<typename T, typename V>

void limbo::solvers::MinCostFlow< T, V >::buildGraph ( )

protected

build min-cost flow graph

Definition at line 294 of file MinCostFlow.h.

◆ costMap()

template<typename T, typename V>

MinCostFlow< T, V >::arc_cost_map_type const & limbo::solvers::MinCostFlow< T, V >::costMap ( ) const

Returns: arc cost map

Definition at line 189 of file MinCostFlow.h.

◆ flowMap()

template<typename T, typename V>

MinCostFlow< T, V >::arc_flow_map_type & limbo::solvers::MinCostFlow< T, V >::flowMap ( )

Returns: arc flow map

Definition at line 199 of file MinCostFlow.h.

◆ graph()

template<typename T, typename V>

MinCostFlow< T, V >::graph_type const & limbo::solvers::MinCostFlow< T, V >::graph ( ) const

Returns: graph

Definition at line 174 of file MinCostFlow.h.

◆ lowerMap()

template<typename T, typename V>

MinCostFlow< T, V >::arc_value_map_type const & limbo::solvers::MinCostFlow< T, V >::lowerMap ( ) const

Returns: arc lower bound map

Definition at line 179 of file MinCostFlow.h.

◆ operator()()

template<typename T, typename V>

SolverProperty limbo::solvers::MinCostFlow< T, V >::operator() ( solver_type * solver = NULL )

inline

API to run the algorithm.

Parameters

solver an object to solve min cost flow, use default updater if NULL

Definition at line 110 of file MinCostFlow.h.

◆ operator=()

template<typename T, typename V>

MinCostFlow & limbo::solvers::MinCostFlow< T, V >::operator= ( MinCostFlow< T, V > const & rhs )

protected

assignment, forbidden

Parameters

rhs	right hand side

◆ potentialMap()

template<typename T, typename V>

MinCostFlow< T, V >::node_pot_map_type & limbo::solvers::MinCostFlow< T, V >::potentialMap ( )

Returns: node potential map

Definition at line 204 of file MinCostFlow.h.

◆ printGraph()

template<typename T, typename V>

void limbo::solvers::MinCostFlow< T, V >::printGraph ( bool writeSol ) const

print graph

Parameters

writeSol if true write flow and potential as well

Definition at line 224 of file MinCostFlow.h.

◆ setObjective()

template<typename T, typename V>

void limbo::solvers::MinCostFlow< T, V >::setObjective ( expression_type const & obj )

protected

set objective, support incremental set

Definition at line 426 of file MinCostFlow.h.

◆ setTotalFlowCost()

template<typename T, typename V>

void limbo::solvers::MinCostFlow< T, V >::setTotalFlowCost ( value_type cost )

Parameters

cost	total cost of min-cost flow graph

Definition at line 214 of file MinCostFlow.h.

◆ solve()

template<typename T, typename V>

SolverProperty limbo::solvers::MinCostFlow< T, V >::solve ( solver_type * solver )

protected

kernel function to solve the problem

Parameters

solver an object to solve min cost flow, use default updater if NULL

Definition at line 252 of file MinCostFlow.h.

◆ supplyMap()

template<typename T, typename V>

MinCostFlow< T, V >::node_value_map_type const & limbo::solvers::MinCostFlow< T, V >::supplyMap ( ) const

Returns: node supply map

Definition at line 194 of file MinCostFlow.h.

◆ totalCost()

template<typename T, typename V>

MinCostFlow< T, V >::value_type limbo::solvers::MinCostFlow< T, V >::totalCost ( ) const

Returns: total cost of the original LP problem

Definition at line 219 of file MinCostFlow.h.

◆ totalFlowCost()

template<typename T, typename V>

MinCostFlow< T, V >::value_type limbo::solvers::MinCostFlow< T, V >::totalFlowCost ( ) const

Returns: total flow cost

Definition at line 209 of file MinCostFlow.h.

◆ upperMap()

template<typename T, typename V>

MinCostFlow< T, V >::arc_value_map_type const & limbo::solvers::MinCostFlow< T, V >::upperMap ( ) const

Returns: arc upper bound map

Definition at line 184 of file MinCostFlow.h.

Member Data Documentation

◆ m_graph

template<typename T, typename V>

graph_type limbo::solvers::MinCostFlow< T, V >::m_graph

protected

input graph

Definition at line 162 of file MinCostFlow.h.

◆ m_mCost

template<typename T, typename V>

arc_cost_map_type limbo::solvers::MinCostFlow< T, V >::m_mCost

protected

arc cost in min-cost flow

Definition at line 165 of file MinCostFlow.h.

◆ m_mFlow

template<typename T, typename V>

arc_flow_map_type limbo::solvers::MinCostFlow< T, V >::m_mFlow

protected

solution of min-cost flow, which is the solution of LP

Definition at line 169 of file MinCostFlow.h.

◆ m_mLower

template<typename T, typename V>

arc_value_map_type limbo::solvers::MinCostFlow< T, V >::m_mLower

protected

lower bound of flow, usually zero

Definition at line 163 of file MinCostFlow.h.

◆ m_model

template<typename T, typename V>

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

protected

model for the problem

Definition at line 160 of file MinCostFlow.h.

◆ m_mPotential

template<typename T, typename V>

node_pot_map_type limbo::solvers::MinCostFlow< T, V >::m_mPotential

protected

solution of min-cost flow, which is the dual solution of LP

Definition at line 170 of file MinCostFlow.h.

◆ m_mSupply

template<typename T, typename V>

node_value_map_type limbo::solvers::MinCostFlow< T, V >::m_mSupply

protected

node supply in min-cost flow

Definition at line 166 of file MinCostFlow.h.

◆ m_mUpper

template<typename T, typename V>

arc_value_map_type limbo::solvers::MinCostFlow< T, V >::m_mUpper

protected

upper bound of flow, arc capacity in min-cost flow

Definition at line 164 of file MinCostFlow.h.

◆ m_totalFlowCost

template<typename T, typename V>

value_type limbo::solvers::MinCostFlow< T, V >::m_totalFlowCost

protected

total cost after solving

Definition at line 167 of file MinCostFlow.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/MinCostFlow.h

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ arc_cost_map_type

◆ arc_flow_map_type

◆ arc_name_map_type

◆ arc_type

◆ arc_value_map_type

◆ coefficient_value_type

◆ constraint_type

◆ expression_type

◆ graph_type

◆ model_type

◆ node_name_map_type

◆ node_pot_map_type

◆ node_type

◆ node_value_map_type

◆ property_type

◆ solver_type

◆ term_type

◆ value_type

◆ variable_type

◆ variable_value_type

Constructor & Destructor Documentation

◆ MinCostFlow() [1/2]

◆ ~MinCostFlow()

◆ MinCostFlow() [2/2]

Member Function Documentation

◆ applySolution()

◆ buildGraph()

◆ costMap()

◆ flowMap()

◆ graph()

◆ lowerMap()

◆ operator()()

◆ operator=()

◆ potentialMap()

◆ printGraph()

◆ setObjective()

◆ setTotalFlowCost()

◆ solve()

◆ supplyMap()

◆ totalCost()

◆ totalFlowCost()

◆ upperMap()

Member Data Documentation

◆ m_graph

◆ m_mCost

◆ m_mFlow

◆ m_mLower

◆ m_model

◆ m_mPotential

◆ m_mSupply

◆ m_mUpper

◆ m_totalFlowCost