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

#include <LpDualMcf.h>

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

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

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
Public Types inherited from limbo::solvers::lpmcf::Lgf< int64_t >
typedef int64_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
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\).
virtual void	add_constraint (std::string const &, LpParser::TermArray const &terms, char compare, double constant)
	add constraint callback for LpParser::LpDataBase
virtual void	add_objective (bool minimize, LpParser::TermArray const &terms)
	add object callback for LpParser::LpDataBase
virtual void	add_constraint (string const &xi, string const &xj, cost_type const &cij)
	add constraint \(x_i - x_j \ge c_{ij}\).
virtual void	add_objective (string const &xi, value_type const &w)
	add linear terms for objective function of the primal linear programming problem.
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
void	is_bounded (bool v)
	set if the problem is bounded
alg_type::ProblemType	operator() (string const &filename)
	API to run the algorithm with input file.
alg_type::ProblemType	operator() ()
	API to run the algorithm.
value_type	solution (string const &xi) const
	get solution to \(x_i\)
void	read_lp (string const &filename)
	read lp format
bool	empty () const
	check empty
virtual void	print_solution (string const &filename) const
	print solutions into a file including primal problem and dual problem
void	print_problem (string const &filename) const
	print primal problem in LP format to a file
Public Member Functions inherited from limbo::solvers::lpmcf::Lgf< int64_t >
	Lgf ()
	constructor
virtual	~Lgf ()
	destructor
alg_type::ProblemType	operator() (string const &filename)
	API to run the algorithm.
virtual void	print_graph (string const &filename) const
	print graph
void	read_lgf (string const &lgfFile)
	read input file in .lgf format and initialize graph
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.
virtual void	set_integer (string const &vname, bool binary)=0
	set integer variables

Protected Member Functions
void	prepare ()
	prepare before run
alg_type::ProblemType	run ()
	kernel function to run algorithm
Protected Member Functions inherited from limbo::solvers::lpmcf::Lgf< int64_t >
alg_type::ProblemType	run ()
	run algorithm

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

Member Typedef Documentation

◆ alg_type

template<typename T = int64_t>

typedef base_type1::alg_type limbo::solvers::lpmcf::LpDualMcf< T >::alg_type

Definition at line 163 of file LpDualMcf.h.

◆ base_type1

template<typename T = int64_t>

typedef Lgf<value_type> limbo::solvers::lpmcf::LpDualMcf< T >::base_type1

inherit from limbo::solvers::lpmcf::Lgf

Definition at line 146 of file LpDualMcf.h.

◆ base_type2

template<typename T = int64_t>

typedef LpParser::LpDataBase limbo::solvers::lpmcf::LpDualMcf< T >::base_type2

inherit from LpParser::LpDataBase

Definition at line 148 of file LpDualMcf.h.

◆ value_type

template<typename T = int64_t>

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

value_type can only be integer types

Definition at line 144 of file LpDualMcf.h.

Constructor & Destructor Documentation

◆ LpDualMcf()

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

◆ add_constraint() [1/2]

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.

◆ add_constraint() [2/2]

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.

◆ add_objective() [1/2]

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.

◆ add_objective() [2/2]

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.

◆ add_variable()

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.

◆ empty()

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.

◆ is_bounded() [1/2]

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.

◆ is_bounded() [2/2]

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.

◆ operator()() [1/2]

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.

◆ operator()() [2/2]

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.

◆ prepare()

template<typename T = int64_t>

void limbo::solvers::lpmcf::LpDualMcf< T >::prepare ( )

inlineprotected

prepare before run

Definition at line 513 of file LpDualMcf.h.

◆ print_problem()

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.

◆ print_solution()

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

Definition at line 431 of file LpDualMcf.h.

◆ read_lp()

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.

◆ run()

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.

◆ set_integer()

template<typename T = int64_t>

void limbo::solvers::lpmcf::LpDualMcf< T >::set_integer	(	std::string const &	,
		bool	)

inline

set integer variables param vname integer variables
param binary denotes whether they are binary variables

Definition at line 368 of file LpDualMcf.h.

◆ solution()

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

◆ m_addl_node

template<typename T = int64_t>

node_type limbo::solvers::lpmcf::LpDualMcf< T >::m_addl_node

protected

additional node, only valid when m_is_bounded = true

Definition at line 649 of file LpDualMcf.h.

◆ m_hConstraint

template<typename T = int64_t>

unordered_map<hash_pair<string, string>, constraint_type> limbo::solvers::lpmcf::LpDualMcf< T >::m_hConstraint

protected

constraint map

Definition at line 654 of file LpDualMcf.h.

◆ m_hVariable

template<typename T = int64_t>

unordered_map<string, variable_type> limbo::solvers::lpmcf::LpDualMcf< T >::m_hVariable

protected

variable map

Definition at line 653 of file LpDualMcf.h.

◆ m_is_bounded

template<typename T = int64_t>

bool limbo::solvers::lpmcf::LpDualMcf< T >::m_is_bounded

protected

whether the problem is bounded or not

Definition at line 648 of file LpDualMcf.h.

◆ m_M

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:

/home/abuild/rpmbuild/BUILD/limbo-3.5.4-build/limbo-3.5.4/limbo/solvers/lpmcf/LpDualMcf.h

Classes

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ alg_type

◆ base_type1

◆ base_type2

◆ value_type

Constructor & Destructor Documentation

◆ LpDualMcf()

Member Function Documentation

◆ add_constraint() [1/2]

◆ add_constraint() [2/2]

◆ add_objective() [1/2]

◆ add_objective() [2/2]

◆ add_variable()

◆ empty()

◆ is_bounded() [1/2]

◆ is_bounded() [2/2]

◆ operator()() [1/2]

◆ operator()() [2/2]

◆ prepare()

◆ print_problem()

◆ print_solution()

◆ read_lp()

◆ run()

◆ set_integer()

◆ solution()

Member Data Documentation

◆ m_addl_node

◆ m_hConstraint

◆ m_hVariable

◆ m_is_bounded

◆ m_M