7 #ifndef LIMBO_SOLVERS_MINCOSTFLOW_H
8 #define LIMBO_SOLVERS_MINCOSTFLOW_H
10 #include <lemon/smart_graph.h>
11 #include <lemon/network_simplex.h>
12 #include <lemon/cost_scaling.h>
13 #include <lemon/capacity_scaling.h>
14 #include <lemon/cycle_canceling.h>
15 #include <lemon/lgf_writer.h>
29 template <
typename T,
typename V>
30 class MinCostFlowSolver;
31 template <
typename T,
typename V>
32 class CapacityScaling;
33 template <
typename T,
typename V>
35 template <
typename T,
typename V>
37 template <
typename T,
typename V>
59 template <
typename T,
typename V>
68 typedef variable_value_type value_type;
75 typedef lemon::SmartDigraph graph_type;
76 typedef graph_type::Node node_type;
77 typedef graph_type::Arc arc_type;
78 typedef graph_type::NodeMap<value_type> node_value_map_type;
79 typedef graph_type::NodeMap<std::string> node_name_map_type;
80 typedef graph_type::ArcMap<std::string> arc_name_map_type;
81 typedef graph_type::ArcMap<value_type> arc_value_map_type;
82 typedef graph_type::ArcMap<value_type> arc_cost_map_type;
83 typedef graph_type::ArcMap<value_type> arc_flow_map_type;
84 typedef graph_type::NodeMap<value_type> node_pot_map_type;
112 return solve(solver);
116 graph_type
const&
graph()
const;
118 arc_value_map_type
const&
lowerMap()
const;
120 arc_value_map_type
const&
upperMap()
const;
122 arc_cost_map_type
const&
costMap()
const;
124 node_value_map_type
const&
supplyMap()
const;
140 void printGraph(
bool writeSol)
const;
173 template <
typename T,
typename V>
178 template <
typename T,
typename V>
183 template <
typename T,
typename V>
188 template <
typename T,
typename V>
193 template <
typename T,
typename V>
198 template <
typename T,
typename V>
203 template <
typename T,
typename V>
208 template <
typename T,
typename V>
211 return m_totalFlowCost;
213 template <
typename T,
typename V>
216 m_totalFlowCost = cost;
218 template <
typename T,
typename V>
221 return totalFlowCost();
223 template <
typename T,
typename V>
227 limboPrint(kDEBUG,
"totalFlowCost = %ld, totalCost = %ld\n", (
long)totalFlowCost(), (
long)totalCost());
229 node_name_map_type nodeNameMap (m_graph);
230 for (
unsigned int i = 0, ie = m_model->constraints().size(); i < ie; ++i)
231 nodeNameMap[m_graph.nodeFromId(i)] = m_model->constraintNames().at(i);
232 nodeNameMap[m_graph.nodeFromId(m_graph.maxNodeId())] =
"st";
234 arc_name_map_type arcNameMap (m_graph);
235 for (
unsigned int i = 0, ie = m_model->numVariables(); i < ie; ++i)
236 arcNameMap[m_graph.arcFromId(i)] = m_model->variableName(variable_type(i));
239 lemon::DigraphWriter<graph_type> writer(m_graph,
"debug.lgf");
240 writer.nodeMap(
"supply", m_mSupply)
241 .nodeMap(
"name", nodeNameMap)
242 .arcMap(
"name", arcNameMap)
243 .arcMap(
"capacity_lower", m_mLower)
244 .arcMap(
"capacity_upper", m_mUpper)
245 .arcMap(
"cost", m_mCost);
247 writer.nodeMap(
"potential", m_mPotential)
248 .arcMap(
"flow", m_mFlow);
251 template <
typename T,
typename V>
254 bool defaultSolver =
false;
259 defaultSolver =
true;
263 if (m_model->numVariables() == 0)
268 if (m_graph.nodeNum() == 0)
270 setObjective(m_model->objective());
271 #ifdef DEBUG_MINCOSTFLOW
274 coefficient_value_type totalSupply = 0;
275 for (graph_type::NodeIt it (m_graph); it != lemon::INVALID; ++it)
276 totalSupply += m_mSupply[it];
284 #ifdef DEBUG_MINCOSTFLOW
293 template <
typename T,
typename V>
298 unsigned int numNodes = 0;
299 for (
typename std::vector<constraint_type>::const_iterator it = m_model->constraints().begin(), ite = m_model->constraints().end(); it != ite; ++it)
302 limboAssertMsg(it->sense() ==
'=',
"only support equality constraints %s", m_model->constraintName(*it).c_str());
308 coefficient_value_type totalSupply = 0;
309 m_graph.reserveNode(numNodes+1);
310 for (
unsigned int i = 0, ie = numNodes+1; i < ie; ++i)
313 node_type st = m_graph.nodeFromId(numNodes);
320 unsigned int constrIndex = 0;
321 for (
typename std::vector<constraint_type>::const_iterator it = m_model->constraints().begin(), ite = m_model->constraints().end(); it != ite; ++it)
329 for (
typename std::vector<term_type>::const_iterator itt = constr.
expression().
terms().begin(), itte = constr.
expression().
terms().end(); itt != itte; ++itt)
332 std::pair<unsigned int, unsigned int>
const& value = vVar2Constr[term.
variable().
id()];
365 for (
typename std::vector<term_type>::const_iterator itt = constr.
expression().
terms().begin(), itte = constr.
expression().
terms().end(); itt != itte; ++itt)
368 std::pair<unsigned int, unsigned int>& value = vVar2Constr[term.
variable().
id()];
372 "variable %s appears in more than 1 constraint with coefficient 1", m_model->variableName(term.
variable()).c_str());
373 value.first = constrIndex;
378 "variable %s appears in more than 1 constraint with coefficient -1", m_model->variableName(term.
variable()).c_str());
379 value.second = constrIndex;
384 m_mSupply[m_graph.nodeFromId(constrIndex)] = constr.
rightHandSide();
391 m_mSupply[st] = -totalSupply;
394 m_graph.reserveArc(vVar2Constr.size());
396 unsigned int var = 0;
397 for (std::vector<std::pair<unsigned int, unsigned int> >::const_iterator it = vVar2Constr.begin(), ite = vVar2Constr.end(); it != ite; ++it, ++var)
399 unsigned int constrSrc = it->first;
400 unsigned int constrTgt = it->second;
405 arc = m_graph.addArc(st, m_graph.nodeFromId(constrTgt));
409 arc = m_graph.addArc(m_graph.nodeFromId(constrSrc), st);
413 arc = m_graph.addArc(m_graph.nodeFromId(constrSrc), m_graph.nodeFromId(constrTgt));
415 m_mLower[arc] = m_model->variableLowerBound(m_model->variable(var));
416 m_mUpper[arc] = m_model->variableUpperBound(m_model->variable(var));
417 #ifdef DEBUG_MINCOSTFLOW
425 template <
typename T,
typename V>
428 for (
typename std::vector<term_type>::const_iterator it = obj.
terms().begin(), ite = obj.
terms().end(); it != ite; ++it)
431 switch (m_model->optimizeType())
445 template <
typename T,
typename V>
449 for (
typename std::vector<value_type>::iterator it = m_model->variableSolutions().begin(), ite = m_model->variableSolutions().end(); it != ite; ++it, ++i)
450 *it = m_mFlow[m_graph.arcFromId(i)];
456 template <
typename T,
typename V>
493 template <
typename T,
typename V>
494 class CapacityScaling :
public MinCostFlowSolver<T, V>
504 typedef lemon::CapacityScaling<
typename primalsolver_type::graph_type,
539 alg_type alg (d->
graph());
542 typename alg_type::ProblemType status = alg.resetParams()
589 template <
typename T,
typename V>
590 class CostScaling :
public MinCostFlowSolver<T, V>
600 typedef lemon::CostScaling<
typename primalsolver_type::graph_type,
607 CostScaling(
typename alg_type::Method method = alg_type::PARTIAL_AUGMENT,
int factor = 16)
637 alg_type alg (d->
graph());
640 typename alg_type::ProblemType status = alg.resetParams()
689 template <
typename T,
typename V>
690 class NetworkSimplex :
public MinCostFlowSolver<T, V>
700 typedef lemon::NetworkSimplex<
typename primalsolver_type::graph_type,
735 alg_type alg (d->
graph());
738 typename alg_type::ProblemType status = alg.resetParams()
785 template <
typename T,
typename V>
786 class CycleCanceling :
public MinCostFlowSolver<T, V>
796 typedef lemon::CycleCanceling<
typename primalsolver_type::graph_type,
831 alg_type alg (d->
graph());
834 typename alg_type::ProblemType status = alg.resetParams()
graph_type const & graph() const
CostScaling & operator=(CostScaling const &rhs)
assignment
Capacity scaling algorithm for min-cost flow.
arc_flow_map_type m_mFlow
solution of min-cost flow, which is the solution of LP
CycleCanceling(CycleCanceling const &rhs)
copy constructor
void applySolution()
apply solutions to model
lemon::CapacityScaling< typename primalsolver_type::graph_type, value_type, value_type > alg_type
algorithm type
value_type totalFlowCost() const
void copy(CapacityScaling const &rhs)
copy object
graph_type m_graph
input graph
Describe properties of a variable.
int m_factor
scaling factor for the algorithm
void setTotalFlowCost(value_type cost)
LP solved with min-cost flow.
SolverProperty
Some enums used in solver.
lemon::CycleCanceling< typename primalsolver_type::graph_type, value_type, value_type > alg_type
algorithm type
coefficient_value_type coefficient() const
NetworkSimplex & operator=(NetworkSimplex const &rhs)
assignment
LinearModel< T, V > model_type
linear model type for the problem
virtual SolverProperty operator()(primalsolver_type *d)
API to run min-cost flow solver.
void buildGraph()
build min-cost flow graph
base_type::primalsolver_type primalsolver_type
dual min-cost flow solver type
arc_value_map_type const & upperMap() const
Basic utilities such as variables and linear expressions in solvers.
CycleCanceling(typename alg_type::Method method=alg_type::CANCEL_AND_TIGHTEN)
constructor
CapacityScaling(int factor=4)
constructor
MinCostFlowSolver< T, V > base_type
base type
Network simplex algorithm for min-cost flow.
value_type m_totalFlowCost
total cost after solving
node_pot_map_type & potentialMap()
virtual ~MinCostFlowSolver()
destructor
V variable_value_type
V variable.
T coefficient_value_type
T coefficient.
lemon::CostScaling< typename primalsolver_type::graph_type, value_type, value_type > alg_type
algorithm type
node_value_map_type m_mSupply
node supply in min-cost flow
alg_type::Method m_method
method for the algorithm, SIMPLE_CYCLE_CANCELING, MINIMUM_MEAN_CYCLE_CANCELING, CANCEL_AND_TIGHTEN ...
MinCostFlowSolver()
constructor
Describe linear constraint.
arc_cost_map_type m_mCost
arc cost in min-cost flow
MinCostFlowSolver< T, V > base_type
base type
virtual SolverProperty operator()(primalsolver_type *d)
API to run min-cost flow solver.
CapacityScaling(CapacityScaling const &rhs)
copy constructor
void setObjective(expression_type const &obj)
set objective, support incremental set
SolverProperty operator()(solver_type *solver=NULL)
API to run the algorithm.
CycleCanceling & operator=(CycleCanceling const &rhs)
assignment
arc_flow_map_type & flowMap()
arc_value_map_type const & lowerMap() const
value_type totalCost() const
virtual SolverProperty operator()(dualsolver_type *d)=0
API to run min-cost flow solver.
lemon::NetworkSimplex< typename primalsolver_type::graph_type, value_type, value_type > alg_type
algorithm type
expression_type const & expression() const
Cycle canceling algorithm for min-cost flow.
CapacityScaling & operator=(CapacityScaling const &rhs)
assignment
void copy(CostScaling const &rhs)
copy object
MinCostFlowSolver< T, V > base_type
base type
virtual SolverProperty operator()(primalsolver_type *d)
API to run min-cost flow solver.
node_value_map_type const & supplyMap() const
int m_factor
scaling factor for the algorithm
base_type::primalsolver_type primalsolver_type
dual min-cost flow solver type
CostScaling(typename alg_type::Method method=alg_type::PARTIAL_AUGMENT, int factor=16)
constructor
MinCostFlow & operator=(MinCostFlow const &rhs)
assignment, forbidden
std::iterator_traits< Iterator >::value_type max(Iterator first, Iterator last)
get max of an array
arc_cost_map_type const & costMap() const
NetworkSimplex(typename alg_type::PivotRule pivotRule=alg_type::BLOCK_SEARCH)
constructor
base_type::primalsolver_type primalsolver_type
dual min-cost flow solver type
coefficient_value_type rightHandSide() const
void copy(CycleCanceling const &rhs)
copy object
NetworkSimplex(NetworkSimplex const &rhs)
copy constructor
alg_type::Method m_method
PUSH, AUGMENT, PARTIAL_AUGMENT.
virtual SolverProperty operator()(primalsolver_type *d)
API to run min-cost flow solver.
void copy(NetworkSimplex const &rhs)
copy object
#define limboAssert(condition)
custom assertion without message
int limboPrint(MessageType m, const char *format,...)
formatted print with prefix
std::vector< term_type > const & terms() const
Cost scaling algorithm for min-cost flow.
MinCostFlowSolver(MinCostFlowSolver const &rhs)
copy constructor
MinCostFlowSolver & operator=(MinCostFlowSolver const &rhs)
assignment
alg_type::PivotRule m_pivotRule
pivot rule for the algorithm, FIRST_ELIGIBLE, BEST_ELIGIBLE, BLOCK_SEARCH, CANDIDATE_LIST, ALTERING_LIST
MinCostFlowSolver< T, V > base_type
base type
void copy(MinCostFlowSolver const &)
copy object
variable_type const & variable() const
model to describe an optimization problem
arc_value_map_type m_mLower
lower bound of flow, usually zero
model_type * m_model
model for the problem
MinCostFlow< T, V > primalsolver_type
dual min-cost flow solver type
#define limboAssertMsg(condition, args...)
custom assertion with message
arc_value_map_type m_mUpper
upper bound of flow, arc capacity in min-cost flow
CostScaling(CostScaling const &rhs)
copy constructor
void scale(coefficient_value_type factor)
scale constraint by a scaling factor
SolverProperty solve(solver_type *solver)
kernel function to solve the problem
MinCostFlow(model_type *model)
constructor
base_type::primalsolver_type primalsolver_type
dual min-cost flow solver type
node_pot_map_type m_mPotential
solution of min-cost flow, which is the dual solution of LP
A base class of min-cost flow solver.