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 More...

~MinCostFlow ()

destructor

SolverProperty operator() (solver_type *solver=NULL)

API to run the algorithm. More...

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

print graph

Parameters

writeSol if true write flow and potential as well

void printGraph (bool writeSol) const

Protected Member Functions
	MinCostFlow (MinCostFlow const &rhs)
	copy constructor, forbidden More...

MinCostFlow &	operator= (MinCostFlow const &rhs)
	assignment, forbidden More...

SolverProperty	solve (solver_type *solver)
	kernel function to solve the problem More...

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.

Constructor & Destructor Documentation

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.

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

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.

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.

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.

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.

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.

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

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.

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.

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.

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.

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.

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.

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.

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

/Users/yibolin/Documents/Projects/Limbo/limbo/solvers/MinCostFlow.h

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

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

Constructor & Destructor Documentation

Member Function Documentation

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