11 #ifndef _LIMBO_SOLVERS_LPMCF_LPDUALMCF_H
12 #define _LIMBO_SOLVERS_LPMCF_LPDUALMCF_H
20 #include <boost/cstdint.hpp>
21 #include <boost/unordered_map.hpp>
22 #include <boost/foreach.hpp>
23 #include <boost/typeof/typeof.hpp>
24 #include <boost/algorithm/string/predicate.hpp>
37 using boost::unordered_map;
54 template <
typename T1,
typename T2>
58 typedef pair<T1, T2> base_type;
59 using typename base_type::first_type;
60 using typename base_type::second_type;
68 hash_pair(first_type
const& a, second_type
const& b) : base_type(a, b) {}
77 {
return this->first == rhs.first && this->second == rhs.second;}
85 boost::hash_combine(seed, key.first);
86 boost::hash_combine(seed, key.second);
139 template <
typename T =
int64_t>
150 using typename base_type1::cost_type;
151 using typename base_type1::graph_type;
152 using typename base_type1::node_type;
153 using typename base_type1::arc_type;
154 using typename base_type1::node_value_map_type;
155 using typename base_type1::node_name_map_type;
156 using typename base_type1::arc_value_map_type;
157 using typename base_type1::arc_cost_map_type;
158 using typename base_type1::arc_flow_map_type;
159 using typename base_type1::node_pot_map_type;
163 typedef typename base_type1::alg_type alg_type;
187 value_type
const& l = 0,
189 value_type
const& w = 0,
190 value_type
const& v = 0)
191 : name(n), range(make_pair(l, r)), weight(w), value(v) {}
220 : variable(make_pair(xi, xj)), constant(c) {}
247 if (l <= (
double)limbo::lowest<value_type>())
248 lb = limbo::lowest<value_type>();
251 assert_msg(lb <= ub,
"failed to add bound " << lb <<
" <= " << xi <<
" <= " << ub);
257 "failed to insert variable " << xi <<
" to hash table");
260 found->second.range.first =
std::max(found->second.range.first, (value_type)lb);
261 found->second.range.second =
std::min(found->second.range.second, (value_type)ub);
262 assert_msg(found->second.range.first <= found->second.range.second,
263 "failed to set bound " << found->second.range.first <<
" <= " << xi <<
" <= " << found->second.range.second);
276 assert(terms.size() == 2 && terms[0].coef*terms[1].coef < 0);
280 string xi = terms[0].var;
281 string xj = terms[1].var;
282 if (compare ==
'<' || compare ==
'=')
284 if (terms[0].coef > 0)
294 constant = -constant;
297 if (compare ==
'>' || compare ==
'=')
299 if (terms[0].coef > 0)
317 for (LpParser::TermArray::const_iterator it = terms.begin(); it != terms.end(); ++it)
335 virtual void add_constraint(
string const& xi,
string const& xj, cost_type
const& cij)
345 "failed to add constraint for " << xi <<
" - " << xj <<
" >= " << cij
348 found->second.constant =
std::max(found->second.constant, cij);
363 found->second.weight += w;
385 typename alg_type::ProblemType
operator()(
string const& filename)
388 typename alg_type::ProblemType status = (*this)();
415 return found->second.value;
435 std::ofstream out (filename.c_str(), std::ios::app);
438 cout <<
"failed to open " << filename << endl;
442 out <<
"############# LP Solution #############" << endl;
455 std::ofstream out (filename.c_str());
458 cout <<
"failed to open " << filename << endl;
467 if (variable.
weight == 0)
continue;
469 out <<
"\t" <<
" + " << variable.
weight <<
" " << variable.
name << endl;
472 out <<
"Subject To\n";
476 out <<
"\t" << constraint.
variable.first
477 <<
" - " << constraint.
variable.second
478 <<
" >= " << constraint.
constant << endl;
487 if (variable.
range.first != limbo::lowest<value_type>()
489 out << variable.
range.first <<
" <= "
490 << variable.
name <<
" <= " << variable.
range.second << endl;
492 else if (variable.
range.first != limbo::lowest<value_type>())
493 out << variable.
name <<
" >= " << variable.
range.first << endl;
496 out << variable.
name <<
" <= " << variable.
range.second << endl;
499 out << variable.
name <<
" free\n";
506 out <<
"\t" << variable.
name << endl;
520 node_type
const& node = this->
m_graph.addNode();
521 variable.
node = node;
540 node_type
const& node1 = variable1.
node;
541 node_type
const& node2 = variable2.
node;
543 arc_type
const& arc = this->
m_graph.addArc(node1, node2);
544 constraint.
arc = arc;
558 value_type addl_weight = 0;
560 addl_weight -= it->second.weight;
562 this->m_hName[
m_addl_node] =
"lpmcf_additional_node";
590 typename alg_type::ProblemType
run()
601 typename alg_type::ProblemType status = alg.reset().resetParams()
613 cout <<
"OPTIMAL" << endl;
616 cout <<
"INFEASIBLE" << endl;
619 cout <<
"UNBOUNDED" << endl;
628 this->
m_totalcost = alg.template totalCost<cost_type>();
632 alg.potentialMap(this->
m_hPot);
635 value_type addl_value = 0;
arc_type arc
arc in the graph
bool is_lower_bounded() const
check if the variable is lower bounded
arc_flow_map_type m_hFlow
solution of min-cost flow, which is the dual solution of LP
Base class for lp database. Only pure virtual functions are defined. User needs to inheritate this cl...
graph_type m_graph
input graph
virtual void print_solution(string const &filename) const
print solution
hash_pair(base_type const &rhs)
copy constructor
node_name_map_type m_hName
node name in mcf
node_value_map_type m_hSupply
node supply in mcf
void prepare()
prepare before run
virtual void add_objective(string const &xi, value_type const &w)
add linear terms for objective function of the primal linear programming problem. ...
alg_type::ProblemType run()
kernel function to run algorithm
std::vector< Term > TermArray
array of terms
variable_type(string const &n, value_type const &l=0, value_type const &r=std::numeric_limits< value_type >::max(), value_type const &w=0, value_type const &v=0)
constructor
virtual void add_constraint(string const &xi, string const &xj, cost_type const &cij)
add constraint .
constraint object in the primal linear programming problem. standard format: maps to arc ...
cost_type m_totalcost
total cost after solving
arc_cost_map_type m_hCost
arc cost in mcf
LpDualMcf(value_type max_limit=(value_type(2)<< (sizeof(value_type)*8 *3/4)))
constructor
value_type weight
weight in the objective, i.e.,
pair< value_type, value_type > range
pair of
alg_type::ProblemType operator()(string const &filename)
API to run the algorithm with input file.
T value_type
value_type can only be integer types
solve network flow graph with min-cost flow
virtual void add_objective(bool minimize, LpParser::TermArray const &terms)
add object callback for LpParser::LpDataBase
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 .
node_pot_map_type m_hPot
dual solution of min-cost flow, which is the solution of LP
constraint_type(string const &xi, string const &xj, value_type const &c)
constructor
arc_value_map_type m_hLower
lower bound of flow, usually zero
mathematical utilities such as abs
bool empty() const
check empty
value_type constant
constant in the right hand side, i.e.,
bool operator==(base_type const &rhs) const
override equality comparison
pair< string, string > variable
variable and
void set_integer(std::string const &, bool)
set integer variables param vname integer variables param binary denotes whether they are binary vari...
string name
name of variable
bool iequals(string const &s1, string const &s2)
check two strings equal, case-insensitive
std::iterator_traits< Iterator >::value_type max(Iterator first, Iterator last)
get max of an array
virtual void print_solution(string const &filename) const
print solutions into a file including primal problem and dual problem
solve linear programming with min-cost flow
alg_type::ProblemType operator()()
API to run the algorithm.
node_type node
node in the graph
void print_problem(string const &filename) const
print primal problem in LP format to a file
virtual void add_constraint(std::string const &, LpParser::TermArray const &terms, char compare, double constant)
add constraint callback for LpParser::LpDataBase
bool is_upper_bounded() const
check if the variable is upper bounded
hash_pair(first_type const &a, second_type const &b)
constructor
unordered_map< string, variable_type > m_hVariable
variable map
Lgf< value_type > base_type1
inherit from limbo::solvers::lpmcf::Lgf
node_type m_addl_node
additional node, only valid when m_is_bounded = true
double lowest< double >()
specialization for floating point types
void read_lp(string const &filename)
read lp format
friend std::size_t hash_value(base_type const &key)
compute hash value for a pair of data
virtual void print_graph(string const &filename) const
print graph
bool is_bounded() const
check if lp problem is bounded
unordered_map< hash_pair< string, string >, constraint_type > m_hConstraint
constraint map
bool is_bounded() const
check if the variable is bounded
arc_value_map_type m_hUpper
upper bound of flow, arc capacity in mcf
variable in the primal linear programming problem. standard format: maps to node ...
std::iterator_traits< Iterator >::value_type min(Iterator first, Iterator last)
get min of an array
hash calculator for pairs
bool read(LpDataBase &db, const string &lpFile)
API for LpParser. Read LP file and initialize database by calling user-defined callback functions...
value_type solution(string const &xi) const
get solution to
LP solved with min-cost flow.
void is_bounded(bool v)
set if the problem is bounded
#define assert_msg(condition, message)
assertion with message
LpParser::LpDataBase base_type2
inherit from LpParser::LpDataBase
value_type value
solved value
bool m_is_bounded
whether the problem is bounded or not