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

#include <LpDualMcf.h>

Inheritance diagram for limbo::solvers::lpmcf::LpDualMcf< T >:

Classes
class	constraint_type
	constraint object in the primal linear programming problem. standard format: \(x_i - x_j \ge c_{ij}\) maps to arc \(x_i \rightarrow x_j, \textrm{cost} = -c_{ij}\). More...

class	variable_type
	variable \(x_i\) in the primal linear programming problem. standard format: \(l_i \le x_i \le u_i\) maps to node \(i\), arcs from node \(i\) to node \(st\). More...

Public Types
typedef T	value_type
	value_type can only be integer types

typedef Lgf< value_type >	base_type1
	inherit from limbo::solvers::lpmcf::Lgf

typedef LpParser::LpDataBase	base_type2
	inherit from LpParser::LpDataBase


typedef base_type1::alg_type	alg_type

typedef value_type	cost_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 < 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

Public Types inherited from limbo::solvers::lpmcf::Lgf< T >
typedef T	value_type

typedef value_type	cost_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 < 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 lemon::NetworkSimplex < graph_type, value_type, cost_type >	alg_network_simplex_type

typedef lemon::CostScaling < graph_type, value_type, cost_type >	alg_cost_scaling_type

typedef alg_cost_scaling_type	alg_type

Public Member Functions
	LpDualMcf (value_type max_limit=(value_type(2)<< (sizeof(value_type)8 3/4)))
	constructor More...

virtual void	add_variable (string const &xi, double l=limbo::lowest< double >(), double r=std::numeric_limits< value_type >::max())
	add variable with range. default range is \(-\infty \le x_i \le \infty\). More...

virtual void	add_constraint (std::string const &, LpParser::TermArray const &terms, char compare, double constant)
	add constraint callback for LpParser::LpDataBase More...

virtual void	add_objective (bool minimize, LpParser::TermArray const &terms)
	add object callback for LpParser::LpDataBase More...

virtual void	add_constraint (string const &xi, string const &xj, cost_type const &cij)
	add constraint \(x_i - x_j \ge c_{ij}\). More...

virtual void	add_objective (string const &xi, value_type const &w)
	add linear terms for objective function of the primal linear programming problem. More...

void	set_integer (std::string const &, bool)
	set integer variables param vname integer variables param binary denotes whether they are binary variables

bool	is_bounded () const
	check if lp problem is bounded More...

void	is_bounded (bool v)
	set if the problem is bounded More...

alg_type::ProblemType	operator() (string const &filename)
	API to run the algorithm with input file. More...

alg_type::ProblemType	operator() ()
	API to run the algorithm. More...

value_type	solution (string const &xi) const
	get solution to \(x_i\) More...

void	read_lp (string const &filename)
	read lp format More...

bool	empty () const
	check empty More...

virtual void	print_solution (string const &filename) const
	print solutions into a file including primal problem and dual problem More...

void	print_problem (string const &filename) const
	print primal problem in LP format to a file More...

Public Member Functions inherited from limbo::solvers::lpmcf::Lgf< T >
	Lgf ()
	constructor

virtual	~Lgf ()
	destructor

alg_type::ProblemType	operator() (string const &filename)
	API to run the algorithm. More...

virtual void	print_graph (string const &filename) const
	print graph More...

void	read_lgf (string const &lgfFile)
	read input file in .lgf format and initialize graph More...

Public Member Functions inherited from LpParser::LpDataBase
virtual void	add_constraint (string const &cname, TermArray const &terms, char compare, double constant)=0
	add constraint that terms compare constant. More...

virtual void	set_integer (string const &vname, bool binary)=0
	set integer variables More...

Protected Member Functions
void	prepare ()
	prepare before run

alg_type::ProblemType	run ()
	kernel function to run algorithm More...

Protected Member Functions inherited from limbo::solvers::lpmcf::Lgf< T >
alg_type::ProblemType	run ()
	run algorithm More...

Protected Attributes
bool	m_is_bounded
	whether the problem is bounded or not

node_type	m_addl_node
	additional node, only valid when m_is_bounded = true

value_type	m_M

unordered_map< string, variable_type >	m_hVariable
	variable map

unordered_map< hash_pair < string, string > , constraint_type >	m_hConstraint
	constraint map

Protected Attributes inherited from limbo::solvers::lpmcf::Lgf< T >
graph_type	m_graph
	input graph

arc_value_map_type	m_hLower
	lower bound of flow, usually zero

arc_value_map_type	m_hUpper
	upper bound of flow, arc capacity in mcf

arc_cost_map_type	m_hCost
	arc cost in mcf

node_value_map_type	m_hSupply
	node supply in mcf

node_name_map_type	m_hName
	node name in mcf

cost_type	m_totalcost
	total cost after solving

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

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

Detailed Description

template<typename T = int64_t>
class limbo::solvers::lpmcf::LpDualMcf< T >

LP solved with min-cost flow.

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, \\ & s.t. & x_i - x_j \ge b_{ij}, \forall (i, j) \in E, \\ & & d_i \le x_i \le u_i, \forall i \in [1, n]. \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), \\ & s.t. & y_i - y_j \ge b_{ij}, \forall (i, j) \in E \\ & & d_i \le y_i - y_0 \le u_i, \forall i \in [1, n], \\ & & y_i \textrm{ is unbounded integer}, \forall i \in [0, n]. \end{eqnarray*}
Re-write the problem

\begin{eqnarray*} & min. & \sum_{i=0}^{n} c_i \cdot y_i, \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]. \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, \infty]\).

Caution: the cost-scaling algorithm in lemon cannot take an arc with negative cost but unlimited capacity. So here I introduce a member variable m_M to represent unlimit, but it is much smaller than real bound of integer. But there may be problem if potential overflow appears.

Template Parameters

T data type

Definition at line 140 of file LpDualMcf.h.

Constructor & Destructor Documentation

template<typename T = int64_t>

limbo::solvers::lpmcf::LpDualMcf< T >::LpDualMcf ( value_type max_limit = (value_type(2) << (sizeof(value_type)*8*3/4)) )

inline

constructor

Parameters

max_limit represents unlimited arc capacity, default value is \(2^{32 \times \frac{3}{4}}\) for int32_t, \(2^{64 \times \frac{3}{4}}\) for int64_t...

Definition at line 225 of file LpDualMcf.h.

Member Function Documentation

template<typename T = int64_t>

virtual void limbo::solvers::lpmcf::LpDualMcf< T >::add_constraint	(	std::string const &	,
		LpParser::TermArray const &	terms,
		char	compare,
		double	constant
	)

inlinevirtual

add constraint callback for LpParser::LpDataBase

Parameters

terms	array of terms in left hand side
compare	operator '<', '>', '='
constant	constant in the right hand side

Definition at line 274 of file LpDualMcf.h.

template<typename T = int64_t>

virtual void limbo::solvers::lpmcf::LpDualMcf< T >::add_constraint	(	string const &	xi,
		string const &	xj,
		cost_type const &	cij
	)

inlinevirtual

add constraint \(x_i - x_j \ge c_{ij}\).

Assume there's no duplicate.

Parameters

xi	variable \(x_i\)
xj	variable \(x_j\)
cij	constant \(c_{ij}\)

Definition at line 335 of file LpDualMcf.h.

template<typename T = int64_t>

virtual void limbo::solvers::lpmcf::LpDualMcf< T >::add_objective	(	bool	minimize,
		LpParser::TermArray const &	terms
	)

inlinevirtual

add object callback for LpParser::LpDataBase

Parameters

minimize	true denotes minimizing object, false denotes maximizing object
terms	array of terms

Implements LpParser::LpDataBase.

Definition at line 315 of file LpDualMcf.h.

template<typename T = int64_t>

virtual void limbo::solvers::lpmcf::LpDualMcf< T >::add_objective	(	string const &	xi,
		value_type const &	w
	)

inlinevirtual

add linear terms for objective function of the primal linear programming problem.

Assume the variable is already been setup. We allow repeat adding weight and the weight will be accumulated.

Parameters

xi	variable \(x_i\)
w	weight

Definition at line 356 of file LpDualMcf.h.

template<typename T = int64_t>

virtual void limbo::solvers::lpmcf::LpDualMcf< T >::add_variable	(	string const &	xi,
		double	l = `limbo::lowest<double>()`,
		double	r = `std::numeric_limits<value_type>::max()`
	)

inlinevirtual

add variable with range. default range is \(-\infty \le x_i \le \infty\).

Parameters

xi	variable \(x_i\)
l	lower bound \(l_i\)
r	upper bound \(u_i\)

Implements LpParser::LpDataBase.

Definition at line 240 of file LpDualMcf.h.

template<typename T = int64_t>

bool limbo::solvers::lpmcf::LpDualMcf< T >::empty ( ) const

inline

check empty

Returns: true if there's no variable created

Definition at line 426 of file LpDualMcf.h.

template<typename T = int64_t>

bool limbo::solvers::lpmcf::LpDualMcf< T >::is_bounded ( ) const

inline

check if lp problem is bounded

Returns: true if the problem is bounded

Definition at line 375 of file LpDualMcf.h.

template<typename T = int64_t>

void limbo::solvers::lpmcf::LpDualMcf< T >::is_bounded ( bool v )

inline

set if the problem is bounded

Parameters

v	flag for whether the problem is bounded

Definition at line 378 of file LpDualMcf.h.

template<typename T = int64_t>

alg_type::ProblemType limbo::solvers::lpmcf::LpDualMcf< T >::operator() ( string const & filename )

inline

API to run the algorithm with input file.

Read primal problem in lp format and then dump solution.

Parameters

filename input file name, the output file will be dumped to filename+".sol"

Returns: solving status

Definition at line 385 of file LpDualMcf.h.

template<typename T = int64_t>

alg_type::ProblemType limbo::solvers::lpmcf::LpDualMcf< T >::operator() ( )

inline

API to run the algorithm.

Execute solver and write out solution file if provided.

Returns: solving status

Definition at line 399 of file LpDualMcf.h.

template<typename T = int64_t>

void limbo::solvers::lpmcf::LpDualMcf< T >::print_problem ( string const & filename ) const

inline

print primal problem in LP format to a file

Parameters

filename output file name

Definition at line 453 of file LpDualMcf.h.

template<typename T = int64_t>

virtual void limbo::solvers::lpmcf::LpDualMcf< T >::print_solution ( string const & filename ) const

inlinevirtual

print solutions into a file including primal problem and dual problem

Parameters

filename output file name

Reimplemented from limbo::solvers::lpmcf::Lgf< T >.

Definition at line 431 of file LpDualMcf.h.

template<typename T = int64_t>

void limbo::solvers::lpmcf::LpDualMcf< T >::read_lp ( string const & filename )

inline

read lp format

Parameters

filename input file in lp format initializing graph

Definition at line 420 of file LpDualMcf.h.

template<typename T = int64_t>

alg_type::ProblemType limbo::solvers::lpmcf::LpDualMcf< T >::run ( )

inlineprotected

kernel function to run algorithm

Returns: solving status, OPTIMAL, INFEASIBLE, UNBOUNDED

Definition at line 590 of file LpDualMcf.h.

template<typename T = int64_t>

value_type limbo::solvers::lpmcf::LpDualMcf< T >::solution ( string const & xi ) const

inline

get solution to \(x_i\)

Parameters

xi	variable \(x_i\)

Returns: solution

Definition at line 410 of file LpDualMcf.h.

Member Data Documentation

template<typename T = int64_t>

value_type limbo::solvers::lpmcf::LpDualMcf< T >::m_M

protected

a very large number to deal with ranges of variables reference from MIT paper: solving the convex cost integer dual network flow problem

Definition at line 651 of file LpDualMcf.h.

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

/Users/yibolin/Documents/Projects/Limbo/limbo/solvers/lpmcf/LpDualMcf.h

Classes

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

template<typename T = int64_t> class limbo::solvers::lpmcf::LpDualMcf< T >

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<typename T = int64_t>
class limbo::solvers::lpmcf::LpDualMcf< T >