LP solved with min-cost flow. A better implementation of limbo::solvers::lpmcf::LpDualMcf. More...

#include <DualMinCostFlow.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< 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
	DualMinCostFlow (model_type *model)
	constructor
	~DualMinCostFlow ()
	destructor
SolverProperty	operator() (solver_type *solver=NULL)
	API to run the algorithm.
value_type	diffBigM () const
void	setDiffBigM (value_type v)
	set big M as a large number for differential constraints
value_type	boundBigM () const
void	setBoundBigM (value_type v)
	set big M as a large number for bound constraints
graph_type const &	graph () 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
	DualMinCostFlow (DualMinCostFlow const &rhs)
	copy constructor, forbidden
DualMinCostFlow &	operator= (DualMinCostFlow const &rhs)
	assignment, forbidden
SolverProperty	solve (solver_type *solver)
	kernel function to solve the problem
void	prepare ()
	prepare data like big M
void	buildGraph ()
	build dual min-cost flow graph
void	mapObjective2Graph ()
	map variables and the objective to graph nodes
unsigned int	mapDiffConstraint2Graph (bool countArcs)
	map differential constraints to graph arcs
unsigned int	mapBoundConstraint2Graph (bool countArcs)
	map bound constraints to graph arcs
void	addArcForDiffConstraint (node_type xi, node_type xj, value_type cij, value_type bigM)
	generalized method to add an arc for differential constraint \( x_i - x_j \ge c_{ij} \), resolve negative arc costs by arc reversal
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_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
value_type	m_diffBigM
	a big number for infinity for differential constraints
value_type	m_boundBigM
	a big number for infinity for bound constraints
value_type	m_reversedArcFlowCost
	normalized flow cost of overall reversed arcs to resolve negative arc cost, to get total flow cost of reversed arcs, it needs to times with big M
arc_flow_map_type	m_mFlow
	solution of min-cost flow, which is the dual solution of LP
node_pot_map_type	m_mPotential
	dual solution of min-cost flow, which is the solution of LP

Detailed Description

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

LP solved with min-cost flow. A better implementation of limbo::solvers::lpmcf::LpDualMcf.

The dual problem of this LP is a min-cost flow problem, so we can solve the graph problem and then call shortest path algrithm to calculate optimum of primal problem.

Primal problem

\begin{eqnarray*}& min. & \sum_{i=1}^{n} c_i \cdot x_i - \sum_{i,j} u_{ij} \alpha_{ij}, \\ & s.t. & x_i - x_j - \alpha_{ij} \ge b_{ij}, \forall (i, j) \in E, \\ & & d_i \le x_i \le u_i, \forall i \in [1, n], \\ & & \alpha_{ij} \ge 0, \forall (i, j) \in A. \end{eqnarray*}
Introduce new variables \(y_i\) in \([0, n]\), set \(x_i = y_i - y_0\),

\begin{eqnarray*}& min. & \sum_{i=1}^{n} c_i \cdot (y_i-y_0) - \sum_{i,j} u_{ij} \alpha_{ij}, \\ & s.t. & y_i - y_j -\alpha_{ij} \ge b_{ij}, \forall (i, j) \in E \\ & & d_i \le y_i - y_0 - \alpha_{ij} \le u_i, \forall i \in [1, n], \\ & & y_i \textrm{ is unbounded integer}, \forall i \in [0, n], \\ & & \alpha_{ij} \ge 0, \forall (i, j) \in A. \end{eqnarray*}
Re-write the problem

\begin{eqnarray*}& min. & \sum_{i=0}^{n} c_i \cdot y_i - \sum_{i,j} u_{ij} \alpha_{ij}, \textrm{ where } \ c_i = \left\{\begin{array}{lr} c_i, & \forall i \in [1, n], \\ - \sum_{j=1}^{n} c_i, & i = 0, \end{array}\right. \\ & s.t. & y_i - y_j \ge \ \left\{\begin{array}{lr} b_{ij}, & \forall (i, j) \in E, \\ d_i, & \forall j = 0, i \in [1, n], \\ -u_i, & \forall i = 0, j \in [1, n], \end{array}\right. \\ & & y_i \textrm{ is unbounded integer}, \forall i \in [0, n], \\ & & \alpha_{ij} \ge 0, \forall (i, j) \in A. \end{eqnarray*}
Map to dual min-cost flow problem.
Let's use \(c'_i\) for generalized \(c_i\) and \(b'_{ij}\) for generalized \(b_{ij}\).
Then \(c'_i\) is node supply. For each \((i, j) \in E'\), an arc from i to j with cost \(-b'_{ij}\) and flow range \([0, u_{ij}]\). The variable \(\alpha_{ij}\) denotes the slackness in the primal problem, but the capacity constraint in the dual problem. We can set the edge capacity as \(u_{ij}\). We can also leave the edge uncapacited ( \(\infty\)) if there are no such variables.
Some concolusions from [FLOW_B2005_Ahuja] where \(f_{ij}^*\) denotes the optimal flow on edge \((i, j)\) and \(c_{ij}^\pi\) denotes the reduced cost in the residual network.
- If \(c_{ij}^\pi > 0\), then \(f_{ij}^* = 0\).
- If \( 0 < f_{ij}^* < u_{ij} \), then \( c_{ij}^\pi = 0 \).
- If \(c_{ij}^\pi < 0\), then \(f_{ij}^* = u_{ij}\).
These conclusions might be useful to check optimality for the primal problem.
Caution: this mapping of LP to dual min-cost flow results may result in negative arc cost which is not supported by all the algorithms (only capacity scaling algorithm supports). Therefore, graph transformation is introduced to convert arcs with negative costs to positive costs with arc inversal.

Template Parameters

T	coefficient type
V	variable type

Definition at line 102 of file DualMinCostFlow.h.

Member Typedef Documentation

◆ arc_cost_map_type

template<typename T, typename V>

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

Definition at line 123 of file DualMinCostFlow.h.

◆ arc_flow_map_type

template<typename T, typename V>

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

Definition at line 124 of file DualMinCostFlow.h.

◆ arc_type

template<typename T, typename V>

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

Definition at line 119 of file DualMinCostFlow.h.

◆ arc_value_map_type

template<typename T, typename V>

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

Definition at line 122 of file DualMinCostFlow.h.

◆ coefficient_value_type

template<typename T, typename V>

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

Definition at line 108 of file DualMinCostFlow.h.

◆ constraint_type

template<typename T, typename V>

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

Definition at line 112 of file DualMinCostFlow.h.

◆ expression_type

template<typename T, typename V>

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

Definition at line 113 of file DualMinCostFlow.h.

◆ graph_type

template<typename T, typename V>

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

Definition at line 117 of file DualMinCostFlow.h.

◆ model_type

template<typename T, typename V>

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

linear model type for the problem

Definition at line 106 of file DualMinCostFlow.h.

◆ node_name_map_type

template<typename T, typename V>

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

Definition at line 121 of file DualMinCostFlow.h.

◆ node_pot_map_type

template<typename T, typename V>

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

Definition at line 125 of file DualMinCostFlow.h.

◆ node_type

template<typename T, typename V>

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

Definition at line 118 of file DualMinCostFlow.h.

◆ node_value_map_type

template<typename T, typename V>

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

Definition at line 120 of file DualMinCostFlow.h.

◆ property_type

template<typename T, typename V>

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

Definition at line 115 of file DualMinCostFlow.h.

◆ solver_type

template<typename T, typename V>

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

Definition at line 127 of file DualMinCostFlow.h.

◆ term_type

template<typename T, typename V>

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

Definition at line 114 of file DualMinCostFlow.h.

◆ value_type

template<typename T, typename V>

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

Definition at line 110 of file DualMinCostFlow.h.

◆ variable_type

template<typename T, typename V>

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

Definition at line 111 of file DualMinCostFlow.h.

◆ variable_value_type

template<typename T, typename V>

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

Definition at line 109 of file DualMinCostFlow.h.

Constructor & Destructor Documentation

◆ DualMinCostFlow() [1/2]

template<typename T, typename V>

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

inline

constructor

Parameters

model pointer to the model of problem

Definition at line 132 of file DualMinCostFlow.h.

◆ ~DualMinCostFlow()

template<typename T, typename V>

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

inline

destructor

Definition at line 147 of file DualMinCostFlow.h.

◆ DualMinCostFlow() [2/2]

template<typename T, typename V>

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

protected

copy constructor, forbidden

Parameters

rhs	right hand side

Member Function Documentation

◆ addArcForDiffConstraint()

template<typename T, typename V>

void limbo::solvers::DualMinCostFlow< T, V >::addArcForDiffConstraint	(	node_type	xi,
		node_type	xj,
		value_type	cij,
		value_type	bigM )

protected

generalized method to add an arc for differential constraint \( x_i - x_j \ge c_{ij} \), resolve negative arc costs by arc reversal

Parameters

xi	node corresponding to variable \( x_i \)
xj	node corresponding to variable \( x_j \)
cij	constant at right hand side
bigM	large number for upper bound of capacity

Definition at line 508 of file DualMinCostFlow.h.

◆ applySolution()

template<typename T, typename V>

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

protected

apply solutions to model

Definition at line 537 of file DualMinCostFlow.h.

◆ boundBigM()

template<typename T, typename V>

DualMinCostFlow< T, V >::value_type limbo::solvers::DualMinCostFlow< T, V >::boundBigM ( ) const

Returns: big M for bound constraints

Definition at line 257 of file DualMinCostFlow.h.

◆ buildGraph()

template<typename T, typename V>

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

protected

build dual min-cost flow graph

Definition at line 406 of file DualMinCostFlow.h.

◆ costMap()

template<typename T, typename V>

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

Returns: arc cost map

Definition at line 282 of file DualMinCostFlow.h.

◆ diffBigM()

template<typename T, typename V>

DualMinCostFlow< T, V >::value_type limbo::solvers::DualMinCostFlow< T, V >::diffBigM ( ) const

Returns: big M for differential constraints

Definition at line 247 of file DualMinCostFlow.h.

◆ flowMap()

template<typename T, typename V>

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

Returns: arc flow map

Definition at line 292 of file DualMinCostFlow.h.

◆ graph()

template<typename T, typename V>

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

Returns: graph

Definition at line 267 of file DualMinCostFlow.h.

◆ mapBoundConstraint2Graph()

template<typename T, typename V>

unsigned int limbo::solvers::DualMinCostFlow< T, V >::mapBoundConstraint2Graph ( bool countArcs )

protected

map bound constraints to graph arcs

Parameters

countArcs flag for counting arcs mode, if true, only count arcs and no actual arcs are added; otherwise, add arcs

Returns: number of arcs added

Definition at line 463 of file DualMinCostFlow.h.

◆ mapDiffConstraint2Graph()

template<typename T, typename V>

unsigned int limbo::solvers::DualMinCostFlow< T, V >::mapDiffConstraint2Graph ( bool countArcs )

protected

map differential constraints to graph arcs

Parameters

countArcs flag for counting arcs mode, if true, only count arcs and no actual arcs are added; otherwise, add arcs

Returns: number of arcs added

Definition at line 434 of file DualMinCostFlow.h.

◆ mapObjective2Graph()

template<typename T, typename V>

void limbo::solvers::DualMinCostFlow< T, V >::mapObjective2Graph ( )

protected

map variables and the objective to graph nodes

Definition at line 423 of file DualMinCostFlow.h.

◆ operator()()

template<typename T, typename V>

SolverProperty limbo::solvers::DualMinCostFlow< 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 153 of file DualMinCostFlow.h.

◆ operator=()

template<typename T, typename V>

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

protected

assignment, forbidden

Parameters

rhs	right hand side

◆ potentialMap()

template<typename T, typename V>

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

Returns: node potential map

Definition at line 297 of file DualMinCostFlow.h.

◆ prepare()

template<typename T, typename V>

void limbo::solvers::DualMinCostFlow< T, V >::prepare ( )

protected

prepare data like big M

Definition at line 383 of file DualMinCostFlow.h.

◆ printGraph()

template<typename T, typename V>

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

print graph

Parameters

writeSol if true write flow and potential as well

Definition at line 319 of file DualMinCostFlow.h.

◆ setBoundBigM()

template<typename T, typename V>

void limbo::solvers::DualMinCostFlow< T, V >::setBoundBigM ( value_type v )

set big M as a large number for bound constraints

Parameters

v value

Definition at line 262 of file DualMinCostFlow.h.

◆ setDiffBigM()

template<typename T, typename V>

void limbo::solvers::DualMinCostFlow< T, V >::setDiffBigM ( value_type v )

set big M as a large number for differential constraints

Parameters

v value

Definition at line 252 of file DualMinCostFlow.h.

◆ setTotalFlowCost()

template<typename T, typename V>

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

Parameters

cost	total cost of min-cost flow graph

Definition at line 307 of file DualMinCostFlow.h.

◆ solve()

template<typename T, typename V>

SolverProperty limbo::solvers::DualMinCostFlow< 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 342 of file DualMinCostFlow.h.

◆ supplyMap()

template<typename T, typename V>

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

Returns: node supply map

Definition at line 287 of file DualMinCostFlow.h.

◆ totalCost()

template<typename T, typename V>

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

Returns: total cost of the original LP problem

Definition at line 312 of file DualMinCostFlow.h.

◆ totalFlowCost()

template<typename T, typename V>

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

Returns: total flow cost

Definition at line 302 of file DualMinCostFlow.h.

◆ upperMap()

template<typename T, typename V>

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

Returns: arc lower bound map; arc upper bound map

Definition at line 277 of file DualMinCostFlow.h.

Member Data Documentation

◆ m_boundBigM

template<typename T, typename V>

value_type limbo::solvers::DualMinCostFlow< T, V >::m_boundBigM

protected

a big number for infinity for bound constraints

Definition at line 239 of file DualMinCostFlow.h.

◆ m_diffBigM

template<typename T, typename V>

value_type limbo::solvers::DualMinCostFlow< T, V >::m_diffBigM

protected

a big number for infinity for differential constraints

Definition at line 238 of file DualMinCostFlow.h.

◆ m_graph

template<typename T, typename V>

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

protected

input graph

Definition at line 232 of file DualMinCostFlow.h.

◆ m_mCost

template<typename T, typename V>

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

protected

arc cost in min-cost flow

Definition at line 235 of file DualMinCostFlow.h.

◆ m_mFlow

template<typename T, typename V>

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

protected

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

Definition at line 242 of file DualMinCostFlow.h.

◆ m_model

template<typename T, typename V>

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

protected

model for the problem

Definition at line 230 of file DualMinCostFlow.h.

◆ m_mPotential

template<typename T, typename V>

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

protected

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

Definition at line 243 of file DualMinCostFlow.h.

◆ m_mSupply

template<typename T, typename V>

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

protected

node supply in min-cost flow

Definition at line 236 of file DualMinCostFlow.h.

◆ m_mUpper

template<typename T, typename V>

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

protected

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

Definition at line 234 of file DualMinCostFlow.h.

◆ m_reversedArcFlowCost

template<typename T, typename V>

value_type limbo::solvers::DualMinCostFlow< T, V >::m_reversedArcFlowCost

protected

normalized flow cost of overall reversed arcs to resolve negative arc cost, to get total flow cost of reversed arcs, it needs to times with big M

Definition at line 240 of file DualMinCostFlow.h.

◆ m_totalFlowCost

template<typename T, typename V>

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

protected

total cost after solving

Definition at line 237 of file DualMinCostFlow.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/DualMinCostFlow.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_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

◆ DualMinCostFlow() [1/2]

◆ ~DualMinCostFlow()

◆ DualMinCostFlow() [2/2]

Member Function Documentation

◆ addArcForDiffConstraint()

◆ applySolution()

◆ boundBigM()

◆ buildGraph()

◆ costMap()

◆ diffBigM()

◆ flowMap()

◆ graph()

◆ mapBoundConstraint2Graph()

◆ mapDiffConstraint2Graph()

◆ mapObjective2Graph()

◆ operator()()

◆ operator=()

◆ potentialMap()

◆ prepare()

◆ printGraph()

◆ setBoundBigM()

◆ setDiffBigM()

◆ setTotalFlowCost()

◆ solve()

◆ supplyMap()

◆ totalCost()

◆ totalFlowCost()

◆ upperMap()

Member Data Documentation

◆ m_boundBigM

◆ m_diffBigM

◆ m_graph

◆ m_mCost

◆ m_mFlow

◆ m_model

◆ m_mPotential

◆ m_mSupply

◆ m_mUpper

◆ m_reversedArcFlowCost

◆ m_totalFlowCost