8 #ifndef LIMBO_SOLVERS_DUALMINCOSTFLOW_H
9 #define LIMBO_SOLVERS_DUALMINCOSTFLOW_H
11 #include <lemon/smart_graph.h>
12 #include <lemon/network_simplex.h>
13 #include <lemon/cost_scaling.h>
14 #include <lemon/capacity_scaling.h>
15 #include <lemon/cycle_canceling.h>
16 #include <lemon/lgf_writer.h>
28 template <
typename T,
typename V>
30 template <
typename T,
typename V>
32 template <
typename T,
typename V>
34 template <
typename T,
typename V>
36 template <
typename T,
typename V>
101 template <
typename T,
typename V>
110 typedef variable_value_type value_type;
117 typedef lemon::SmartDigraph graph_type;
118 typedef graph_type::Node node_type;
119 typedef graph_type::Arc arc_type;
120 typedef graph_type::NodeMap<value_type> node_value_map_type;
121 typedef graph_type::NodeMap<std::string> node_name_map_type;
122 typedef graph_type::ArcMap<value_type> arc_value_map_type;
123 typedef graph_type::ArcMap<value_type> arc_cost_map_type;
124 typedef graph_type::ArcMap<value_type> arc_flow_map_type;
125 typedef graph_type::NodeMap<value_type> node_pot_map_type;
155 return solve(solver);
170 graph_type
const&
graph()
const;
174 arc_value_map_type
const&
upperMap()
const;
176 arc_cost_map_type
const&
costMap()
const;
178 node_value_map_type
const&
supplyMap()
const;
194 void printGraph(
bool writeSol)
const;
246 template <
typename T,
typename V>
251 template <
typename T,
typename V>
256 template <
typename T,
typename V>
261 template <
typename T,
typename V>
266 template <
typename T,
typename V>
276 template <
typename T,
typename V>
281 template <
typename T,
typename V>
286 template <
typename T,
typename V>
291 template <
typename T,
typename V>
296 template <
typename T,
typename V>
301 template <
typename T,
typename V>
304 return m_totalFlowCost;
306 template <
typename T,
typename V>
309 m_totalFlowCost = cost;
311 template <
typename T,
typename V>
316 return -(totalFlowCost()-m_reversedArcFlowCost);
318 template <
typename T,
typename V>
321 limboPrint(kDEBUG,
"diffBigM = %ld, boundBigM = %ld, reversedArcFlowCost = %ld\n", (
long)m_diffBigM, (
long)m_boundBigM, (
long)m_reversedArcFlowCost);
323 limboPrint(kDEBUG,
"totalFlowCost = %ld, totalCost = %ld\n", (
long)totalFlowCost(), (
long)totalCost());
325 node_name_map_type nameMap (m_graph);
326 for (
unsigned int i = 0, ie = m_model->numVariables(); i < ie; ++i)
327 nameMap[m_graph.nodeFromId(i)] = m_model->variableName(variable_type(i));
328 nameMap[m_graph.nodeFromId(m_graph.maxNodeId())] =
"additional";
331 lemon::DigraphWriter<graph_type> writer(m_graph,
"debug.lgf");
332 writer.nodeMap(
"supply", m_mSupply)
333 .nodeMap(
"name", nameMap)
334 .arcMap(
"capacity_upper", m_mUpper)
335 .arcMap(
"cost", m_mCost);
337 writer.nodeMap(
"potential", m_mPotential)
338 .arcMap(
"flow", m_mFlow);
341 template <
typename T,
typename V>
344 bool defaultSolver =
false;
349 defaultSolver =
true;
353 if (m_model->numVariables() == 0)
360 #ifdef DEBUG_DUALMINCOSTFLOW
363 coefficient_value_type totalSupply = 0;
364 for (graph_type::NodeIt it (m_graph); it != lemon::INVALID; ++it)
365 totalSupply += m_mSupply[it];
373 #ifdef DEBUG_DUALMINCOSTFLOW
382 template <
typename T,
typename V>
391 for (
typename std::vector<term_type>::const_iterator it = m_model->objective().terms().begin(), ite = m_model->objective().terms().end(); it != ite; ++it)
393 if (it->coefficient() > 0)
394 m_diffBigM += it->coefficient();
400 m_boundBigM = m_diffBigM<<1;
403 m_reversedArcFlowCost = 0;
405 template <
typename T,
typename V>
409 mapObjective2Graph();
413 unsigned int numArcs = mapDiffConstraint2Graph(
true)+mapBoundConstraint2Graph(
true);
414 m_graph.reserveArc(numArcs);
417 mapDiffConstraint2Graph(
false);
420 mapBoundConstraint2Graph(
false);
422 template <
typename T,
typename V>
427 m_graph.reserveNode(m_model->numVariables()+1);
428 for (
unsigned int i = 0, ie = m_model->numVariables(); i < ie; ++i)
430 for (
typename std::vector<term_type>::const_iterator it = m_model->objective().terms().begin(), ite = m_model->objective().terms().end(); it != ite; ++it)
431 m_mSupply[m_graph.nodeFromId(it->variable().id())] = it->coefficient();
433 template <
typename T,
typename V>
440 unsigned int numArcs = m_model->constraints().size();
444 for (
typename std::vector<constraint_type>::iterator it = m_model->constraints().begin(), ite = m_model->constraints().end(); it != ite; ++it)
450 for (
typename std::vector<constraint_type>::const_iterator it = m_model->constraints().begin(), ite = m_model->constraints().end(); it != ite; ++it)
454 variable_type xi = (vTerm[0].coefficient() > 0)? vTerm[0].variable() : vTerm[1].variable();
455 variable_type xj = (vTerm[0].coefficient() > 0)? vTerm[1].variable() : vTerm[0].variable();
457 addArcForDiffConstraint(m_graph.nodeFromId(xi.
id()), m_graph.nodeFromId(xj.
id()), constr.
rightHandSide(), m_diffBigM);
462 template <
typename T,
typename V>
469 unsigned int numArcs = 0;
470 for (
unsigned int i = 0, ie = m_model->numVariables(); i < ie; ++i)
472 value_type lowerBound = m_model->variableLowerBound(
variable_type(i));
473 value_type upperBound = m_model->variableUpperBound(
variable_type(i));
474 if (lowerBound != limbo::lowest<value_type>())
479 if (!countArcs && numArcs)
483 node_type addlNode = m_graph.addNode();
484 value_type addlWeight = 0;
485 for (
typename std::vector<term_type>::const_iterator it = m_model->objective().terms().begin(), ite = m_model->objective().terms().end(); it != ite; ++it)
486 addlWeight -= it->coefficient();
487 m_mSupply[addlNode] = addlWeight;
491 for (
unsigned int i = 0, ie = m_model->numVariables(); i < ie; ++i)
493 value_type lowerBound = m_model->variableLowerBound(
variable_type(i));
494 value_type upperBound = m_model->variableUpperBound(
variable_type(i));
497 if (lowerBound != limbo::lowest<value_type>())
498 addArcForDiffConstraint(m_graph.nodeFromId(i), addlNode, lowerBound, m_boundBigM);
502 addArcForDiffConstraint(addlNode, m_graph.nodeFromId(i), -upperBound, m_boundBigM);
507 template <
typename T,
typename V>
519 arc_type arc = m_graph.addArc(xi, xj);
522 m_mUpper[arc] = bigM;
526 arc_type arc = m_graph.addArc(xj, xi);
529 m_mUpper[arc] = bigM;
530 m_mSupply[xi] -= bigM;
531 m_mSupply[xj] += bigM;
533 m_reversedArcFlowCost += cij*bigM;
536 template <
typename T,
typename V>
540 value_type addlValue = 0;
541 if ((
unsigned int)m_graph.nodeNum() > m_model->numVariables())
542 addlValue = m_mPotential[m_graph.nodeFromId(m_graph.maxNodeId())];
544 for (
typename std::vector<value_type>::iterator it = m_model->variableSolutions().begin(), ite = m_model->variableSolutions().end(); it != ite; ++it, ++i)
545 *it = m_mPotential[m_graph.nodeFromId(i)]-addlValue;
552 template <
typename T,
typename V>
589 template <
typename T,
typename V>
590 class CapacityScaling :
public MinCostFlowSolver<T, V>
600 typedef lemon::CapacityScaling<
typename dualsolver_type::graph_type,
635 alg_type alg (d->
graph());
638 typename alg_type::ProblemType status = alg.resetParams()
685 template <
typename T,
typename V>
696 typedef lemon::CostScaling<
typename dualsolver_type::graph_type,
703 CostScaling(
typename alg_type::Method method = alg_type::PARTIAL_AUGMENT,
int factor = 16)
733 alg_type alg (d->
graph());
736 typename alg_type::ProblemType status = alg.resetParams()
785 template <
typename T,
typename V>
796 typedef lemon::NetworkSimplex<
typename dualsolver_type::graph_type,
831 alg_type alg (d->
graph());
834 typename alg_type::ProblemType status = alg.resetParams()
881 template <
typename T,
typename V>
892 typedef lemon::CycleCanceling<
typename dualsolver_type::graph_type,
927 alg_type alg (d->
graph());
930 typename alg_type::ProblemType status = alg.resetParams()
CostScaling & operator=(CostScaling const &rhs)
assignment
Capacity scaling algorithm for min-cost flow.
CycleCanceling(CycleCanceling const &rhs)
copy constructor
void copy(CapacityScaling const &rhs)
copy object
virtual SolverProperty operator()(dualsolver_type *d)
API to run min-cost flow solver.
value_type totalCost() const
~DualMinCostFlow()
destructor
Describe properties of a variable.
SolverProperty operator()(solver_type *solver=NULL)
API to run the algorithm.
void applySolution()
apply solutions to model
int m_factor
scaling factor for the algorithm
base_type::dualsolver_type dualsolver_type
dual min-cost flow solver type
SolverProperty
Some enums used in solver.
arc_value_map_type const & upperMap() const
NetworkSimplex & operator=(NetworkSimplex const &rhs)
assignment
virtual SolverProperty operator()(dualsolver_type *d)
API to run min-cost flow solver.
Basic utilities such as variables and linear expressions in solvers.
void buildGraph()
build dual min-cost flow graph
CycleCanceling(typename alg_type::Method method=alg_type::CANCEL_AND_TIGHTEN)
constructor
CapacityScaling(int factor=4)
constructor
node_pot_map_type m_mPotential
dual solution of min-cost flow, which is the solution of LP
MinCostFlowSolver< T, V > base_type
base type
Network simplex algorithm for min-cost flow.
virtual ~MinCostFlowSolver()
destructor
void setTotalFlowCost(value_type cost)
value_type m_reversedArcFlowCost
normalized flow cost of overall reversed arcs to resolve negative arc cost, to get total flow cost of...
SolverProperty solve(solver_type *solver)
kernel function to solve the problem
value_type boundBigM() const
V variable_value_type
V variable.
arc_flow_map_type & flowMap()
arc_cost_map_type m_mCost
arc cost in min-cost flow
value_type totalFlowCost() const
T coefficient_value_type
T coefficient.
graph_type const & graph() const
alg_type::Method m_method
method for the algorithm, SIMPLE_CYCLE_CANCELING, MINIMUM_MEAN_CYCLE_CANCELING, CANCEL_AND_TIGHTEN ...
MinCostFlowSolver()
constructor
void mapObjective2Graph()
map variables and the objective to graph nodes
Describe linear constraint.
arc_value_map_type m_mUpper
upper bound of flow, arc capacity in min-cost flow
virtual SolverProperty operator()(dualsolver_type *d)
API to run min-cost flow solver.
unsigned int mapDiffConstraint2Graph(bool countArcs)
map differential constraints to graph arcs
MinCostFlowSolver< T, V > base_type
base type
lemon::CapacityScaling< typename dualsolver_type::graph_type, value_type, value_type > alg_type
algorithm type
CapacityScaling(CapacityScaling const &rhs)
copy constructor
void setDiffBigM(value_type v)
set big M as a large number for differential constraints
CycleCanceling & operator=(CycleCanceling const &rhs)
assignment
value_type m_boundBigM
a big number for infinity for bound constraints
DualMinCostFlow & operator=(DualMinCostFlow const &rhs)
assignment, forbidden
virtual SolverProperty operator()(dualsolver_type *d)=0
API to run min-cost flow solver.
base_type::dualsolver_type dualsolver_type
dual min-cost flow solver type
node_pot_map_type & potentialMap()
node_value_map_type const & supplyMap() const
arc_flow_map_type m_mFlow
solution of min-cost flow, which is the dual solution of LP
expression_type const & expression() const
Cycle canceling algorithm for min-cost flow.
node_value_map_type m_mSupply
node supply in min-cost flow
CapacityScaling & operator=(CapacityScaling const &rhs)
assignment
base_type::dualsolver_type dualsolver_type
dual min-cost flow solver type
model_type * m_model
model for the problem
void copy(CostScaling const &rhs)
copy object
DualMinCostFlow(model_type *model)
constructor
MinCostFlowSolver< T, V > base_type
base type
value_type m_diffBigM
a big number for infinity for differential constraints
LinearModel< T, V > model_type
linear model type for the problem
lemon::CostScaling< typename dualsolver_type::graph_type, value_type, value_type > alg_type
algorithm type
void normalize(char s)
normalize sense
int m_factor
scaling factor for the algorithm
CostScaling(typename alg_type::Method method=alg_type::PARTIAL_AUGMENT, int factor=16)
constructor
std::iterator_traits< Iterator >::value_type max(Iterator first, Iterator last)
get max of an array
NetworkSimplex(typename alg_type::PivotRule pivotRule=alg_type::BLOCK_SEARCH)
constructor
coefficient_value_type rightHandSide() const
void copy(CycleCanceling const &rhs)
copy object
unsigned int mapBoundConstraint2Graph(bool countArcs)
map bound constraints to graph arcs
NetworkSimplex(NetworkSimplex const &rhs)
copy constructor
arc_cost_map_type const & costMap() const
alg_type::Method m_method
PUSH, AUGMENT, PARTIAL_AUGMENT.
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
virtual SolverProperty operator()(dualsolver_type *d)
API to run min-cost flow solver.
Cost scaling algorithm for min-cost flow.
void addArcForDiffConstraint(node_type xi, node_type xj, value_type cij, value_type bigM)
generalized method to add an arc for differential constraint , resolve negative arc costs by arc reve...
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 setBoundBigM(value_type v)
set big M as a large number for bound constraints
lemon::NetworkSimplex< typename dualsolver_type::graph_type, value_type, value_type > alg_type
algorithm type
void copy(MinCostFlowSolver const &)
copy object
model to describe an optimization problem
lemon::CycleCanceling< typename dualsolver_type::graph_type, value_type, value_type > alg_type
algorithm type
#define limboAssertMsg(condition, args...)
custom assertion with message
CostScaling(CostScaling const &rhs)
copy constructor
value_type m_totalFlowCost
total cost after solving
void prepare()
prepare data like big M
value_type diffBigM() const
base_type::dualsolver_type dualsolver_type
dual min-cost flow solver type
LP solved with min-cost flow. A better implementation of limbo::solvers::lpmcf::LpDualMcf.
graph_type m_graph
input graph
DualMinCostFlow< T, V > dualsolver_type
dual min-cost flow solver type
A base class of min-cost flow solver.