diff --git a/doc/groups.dox b/doc/groups.dox --- a/doc/groups.dox +++ b/doc/groups.dox @@ -317,15 +317,15 @@ The \e maximum \e flow \e problem is to find a flow of maximum value between a single source and a single target. Formally, there is a \f$G=(V,A)\f$ -digraph, a \f$cap:A\rightarrow\mathbf{R}^+_0\f$ capacity function and +digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and \f$s, t \in V\f$ source and target nodes. -A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the +A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the following optimization problem. -\f[ \max\sum_{a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f] -\f[ \sum_{a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a) - \qquad \forall v\in V\setminus\{s,t\} \f] -\f[ 0 \leq f(a) \leq cap(a) \qquad \forall a\in A \f] +\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f] +\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu) + \quad \forall u\in V\setminus\{s,t\} \f] +\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f] LEMON contains several algorithms for solving maximum flow problems: - \ref EdmondsKarp Edmonds-Karp algorithm. @@ -345,35 +345,103 @@ \brief Algorithms for finding minimum cost flows and circulations. -This group describes the algorithms for finding minimum cost flows and +This group contains the algorithms for finding minimum cost flows and circulations. The \e minimum \e cost \e flow \e problem is to find a feasible flow of minimum total cost from a set of supply nodes to a set of demand nodes -in a network with capacity constraints and arc costs. +in a network with capacity constraints (lower and upper bounds) +and arc costs. Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and -upper bounds for the flow values on the arcs, +upper bounds for the flow values on the arcs, for which +\f$0 \leq lower(uv) \leq upper(uv)\f$ holds for all \f$uv\in A\f$. \f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow -on the arcs, and -\f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values -of the nodes. -A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of -the following optimization problem. +on the arcs, and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the +signed supply values of the nodes. +If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$ +supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with +\f$-sup(u)\f$ demand. +A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}^+_0\f$ solution +of the following optimization problem. -\f[ \min\sum_{a\in A} f(a) cost(a) \f] -\f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) = - supply(v) \qquad \forall v\in V \f] -\f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f] +\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f] +\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq + sup(u) \quad \forall u\in V \f] +\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f] -LEMON contains several algorithms for solving minimum cost flow problems: - - \ref CycleCanceling Cycle-canceling algorithms. - - \ref CapacityScaling Successive shortest path algorithm with optional +The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be +zero or negative in order to have a feasible solution (since the sum +of the expressions on the left-hand side of the inequalities is zero). +It means that the total demand must be greater or equal to the total +supply and all the supplies have to be carried out from the supply nodes, +but there could be demands that are not satisfied. +If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand +constraints have to be satisfied with equality, i.e. all demands +have to be satisfied and all supplies have to be used. + +If you need the opposite inequalities in the supply/demand constraints +(i.e. the total demand is less than the total supply and all the demands +have to be satisfied while there could be supplies that are not used), +then you could easily transform the problem to the above form by reversing +the direction of the arcs and taking the negative of the supply values +(e.g. using \ref ReverseDigraph and \ref NegMap adaptors). +However \ref NetworkSimplex algorithm also supports this form directly +for the sake of convenience. + +A feasible solution for this problem can be found using \ref Circulation. + +Note that the above formulation is actually more general than the usual +definition of the minimum cost flow problem, in which strict equalities +are required in the supply/demand contraints, i.e. + +\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) = + sup(u) \quad \forall u\in V. \f] + +However if the sum of the supply values is zero, then these two problems +are equivalent. So if you need the equality form, you have to ensure this +additional contraint for the algorithms. + +The dual solution of the minimum cost flow problem is represented by node +potentials \f$\pi: V\rightarrow\mathbf{Z}\f$. +An \f$f: A\rightarrow\mathbf{Z}^+_0\f$ feasible solution of the problem +is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$ +node potentials the following \e complementary \e slackness optimality +conditions hold. + + - For all \f$uv\in A\f$ arcs: + - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$; + - if \f$lower(uv) #include +#include +#include +#include namespace lemon { @@ -47,6 +50,8 @@ /// /// In general this class is the fastest implementation available /// in LEMON for the minimum cost flow problem. + /// Moreover it supports both direction of the supply/demand inequality + /// constraints. For more information see \ref ProblemType. /// /// \tparam GR The digraph type the algorithm runs on. /// \tparam F The value type used for flow amounts, capacity bounds @@ -58,7 +63,8 @@ /// be integer. /// /// \note %NetworkSimplex provides five different pivot rule - /// implementations. For more information see \ref PivotRule. + /// implementations, from which the most efficient one is used + /// by default. For more information see \ref PivotRule. template class NetworkSimplex { @@ -68,10 +74,17 @@ typedef F Flow; /// The cost type of the algorithm typedef C Cost; +#ifdef DOXYGEN + /// The type of the flow map + typedef GR::ArcMap FlowMap; + /// The type of the potential map + typedef GR::NodeMap PotentialMap; +#else /// The type of the flow map typedef typename GR::template ArcMap FlowMap; /// The type of the potential map typedef typename GR::template NodeMap PotentialMap; +#endif public: @@ -117,6 +130,58 @@ /// candidate list and extends this list in every iteration. ALTERING_LIST }; + + /// \brief Enum type for selecting the problem type. + /// + /// Enum type for selecting the problem type, i.e. the direction of + /// the inequalities in the supply/demand constraints of the + /// \ref min_cost_flow "minimum cost flow problem". + /// + /// The default problem type is \c GEQ, since this form is supported + /// by other minimum cost flow algorithms and the \ref Circulation + /// algorithm as well. + /// The \c LEQ problem type can be selected using the \ref problemType() + /// function. + /// + /// Note that the equality form is a special case of both problem type. + enum ProblemType { + + /// This option means that there are "greater or equal" + /// constraints in the defintion, i.e. the exact formulation of the + /// problem is the following. + /** + \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f] + \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq + sup(u) \quad \forall u\in V \f] + \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f] + */ + /// It means that the total demand must be greater or equal to the + /// total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or + /// negative) and all the supplies have to be carried out from + /// the supply nodes, but there could be demands that are not + /// satisfied. + GEQ, + /// It is just an alias for the \c GEQ option. + CARRY_SUPPLIES = GEQ, + + /// This option means that there are "less or equal" + /// constraints in the defintion, i.e. the exact formulation of the + /// problem is the following. + /** + \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f] + \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \leq + sup(u) \quad \forall u\in V \f] + \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f] + */ + /// It means that the total demand must be less or equal to the + /// total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or + /// positive) and all the demands have to be satisfied, but there + /// could be supplies that are not carried out from the supply + /// nodes. + LEQ, + /// It is just an alias for the \c LEQ option. + SATISFY_DEMANDS = LEQ + }; private: @@ -155,6 +220,7 @@ bool _pstsup; Node _psource, _ptarget; Flow _pstflow; + ProblemType _ptype; // Result maps FlowMap *_flow_map; @@ -586,13 +652,13 @@ /// \brief Constructor. /// - /// Constructor. + /// The constructor of the class. /// /// \param graph The digraph the algorithm runs on. NetworkSimplex(const GR& graph) : _graph(graph), _plower(NULL), _pupper(NULL), _pcost(NULL), - _psupply(NULL), _pstsup(false), + _psupply(NULL), _pstsup(false), _ptype(GEQ), _flow_map(NULL), _potential_map(NULL), _local_flow(false), _local_potential(false), _node_id(graph) @@ -611,6 +677,12 @@ if (_local_potential) delete _potential_map; } + /// \name Parameters + /// The parameters of the algorithm can be specified using these + /// functions. + + /// @{ + /// \brief Set the lower bounds on the arcs. /// /// This function sets the lower bounds on the arcs. @@ -760,6 +832,20 @@ _pstflow = k; return *this; } + + /// \brief Set the problem type. + /// + /// This function sets the problem type for the algorithm. + /// If it is not used before calling \ref run(), the \ref GEQ problem + /// type will be used. + /// + /// For more information see \ref ProblemType. + /// + /// \return (*this) + NetworkSimplex& problemType(ProblemType problem_type) { + _ptype = problem_type; + return *this; + } /// \brief Set the flow map. /// @@ -795,6 +881,8 @@ _potential_map = ↦ return *this; } + + /// @} /// \name Execution Control /// The algorithm can be executed using \ref run(). @@ -804,10 +892,11 @@ /// \brief Run the algorithm. /// /// This function runs the algorithm. - /// The paramters can be specified using \ref lowerMap(), + /// The paramters can be specified using functions \ref lowerMap(), /// \ref upperMap(), \ref capacityMap(), \ref boundMaps(), - /// \ref costMap(), \ref supplyMap() and \ref stSupply() - /// functions. For example, + /// \ref costMap(), \ref supplyMap(), \ref stSupply(), + /// \ref problemType(), \ref flowMap() and \ref potentialMap(). + /// For example, /// \code /// NetworkSimplex ns(graph); /// ns.boundMaps(lower, upper).costMap(cost) @@ -830,9 +919,10 @@ /// \brief Reset all the parameters that have been given before. /// /// This function resets all the paramaters that have been given - /// using \ref lowerMap(), \ref upperMap(), \ref capacityMap(), - /// \ref boundMaps(), \ref costMap(), \ref supplyMap() and - /// \ref stSupply() functions before. + /// before using functions \ref lowerMap(), \ref upperMap(), + /// \ref capacityMap(), \ref boundMaps(), \ref costMap(), + /// \ref supplyMap(), \ref stSupply(), \ref problemType(), + /// \ref flowMap() and \ref potentialMap(). /// /// It is useful for multiple run() calls. If this function is not /// used, all the parameters given before are kept for the next @@ -869,6 +959,14 @@ _pcost = NULL; _psupply = NULL; _pstsup = false; + _ptype = GEQ; + if (_local_flow) delete _flow_map; + if (_local_potential) delete _potential_map; + _flow_map = NULL; + _potential_map = NULL; + _local_flow = false; + _local_potential = false; + return *this; } @@ -1000,20 +1098,21 @@ // Initialize node related data bool valid_supply = true; + Flow sum_supply = 0; if (!_pstsup && !_psupply) { _pstsup = true; _psource = _ptarget = NodeIt(_graph); _pstflow = 0; } if (_psupply) { - Flow sum = 0; int i = 0; for (NodeIt n(_graph); n != INVALID; ++n, ++i) { _node_id[n] = i; _supply[i] = (*_psupply)[n]; - sum += _supply[i]; + sum_supply += _supply[i]; } - valid_supply = (sum == 0); + valid_supply = (_ptype == GEQ && sum_supply <= 0) || + (_ptype == LEQ && sum_supply >= 0); } else { int i = 0; for (NodeIt n(_graph); n != INVALID; ++n, ++i) { @@ -1021,10 +1120,95 @@ _supply[i] = 0; } _supply[_node_id[_psource]] = _pstflow; - _supply[_node_id[_ptarget]] = -_pstflow; + _supply[_node_id[_ptarget]] = -_pstflow; } if (!valid_supply) return false; + // Infinite capacity value + Flow inf_cap = + std::numeric_limits::has_infinity ? + std::numeric_limits::infinity() : + std::numeric_limits::max(); + + // Initialize artifical cost + Cost art_cost; + if (std::numeric_limits::is_exact) { + art_cost = std::numeric_limits::max() / 4 + 1; + } else { + art_cost = std::numeric_limits::min(); + for (int i = 0; i != _arc_num; ++i) { + if (_cost[i] > art_cost) art_cost = _cost[i]; + } + art_cost = (art_cost + 1) * _node_num; + } + + // Run Circulation to check if a feasible solution exists + typedef ConstMap ConstArcMap; + FlowNodeMap *csup = NULL; + bool local_csup = false; + if (_psupply) { + csup = _psupply; + } else { + csup = new FlowNodeMap(_graph, 0); + (*csup)[_psource] = _pstflow; + (*csup)[_ptarget] = -_pstflow; + local_csup = true; + } + bool circ_result = false; + if (_ptype == GEQ || (_ptype == LEQ && sum_supply == 0)) { + // GEQ problem type + if (_plower) { + if (_pupper) { + Circulation + circ(_graph, *_plower, *_pupper, *csup); + circ_result = circ.run(); + } else { + Circulation + circ(_graph, *_plower, ConstArcMap(inf_cap), *csup); + circ_result = circ.run(); + } + } else { + if (_pupper) { + Circulation + circ(_graph, ConstArcMap(0), *_pupper, *csup); + circ_result = circ.run(); + } else { + Circulation + circ(_graph, ConstArcMap(0), ConstArcMap(inf_cap), *csup); + circ_result = circ.run(); + } + } + } else { + // LEQ problem type + typedef ReverseDigraph RevGraph; + typedef NegMap NegNodeMap; + RevGraph rgraph(_graph); + NegNodeMap neg_csup(*csup); + if (_plower) { + if (_pupper) { + Circulation + circ(rgraph, *_plower, *_pupper, neg_csup); + circ_result = circ.run(); + } else { + Circulation + circ(rgraph, *_plower, ConstArcMap(inf_cap), neg_csup); + circ_result = circ.run(); + } + } else { + if (_pupper) { + Circulation + circ(rgraph, ConstArcMap(0), *_pupper, neg_csup); + circ_result = circ.run(); + } else { + Circulation + circ(rgraph, ConstArcMap(0), ConstArcMap(inf_cap), neg_csup); + circ_result = circ.run(); + } + } + } + if (local_csup) delete csup; + if (!circ_result) return false; + // Set data for the artificial root node _root = _node_num; _parent[_root] = -1; @@ -1033,8 +1217,12 @@ _rev_thread[0] = _root; _succ_num[_root] = all_node_num; _last_succ[_root] = _root - 1; - _supply[_root] = 0; - _pi[_root] = 0; + _supply[_root] = -sum_supply; + if (sum_supply < 0) { + _pi[_root] = -art_cost; + } else { + _pi[_root] = art_cost; + } // Store the arcs in a mixed order int k = std::max(int(sqrt(_arc_num)), 10); @@ -1045,10 +1233,6 @@ } // Initialize arc maps - Flow inf_cap = - std::numeric_limits::has_infinity ? - std::numeric_limits::infinity() : - std::numeric_limits::max(); if (_pupper && _pcost) { for (int i = 0; i != _arc_num; ++i) { Arc e = _arc_ref[i]; @@ -1083,18 +1267,6 @@ } } - // Initialize artifical cost - Cost art_cost; - if (std::numeric_limits::is_exact) { - art_cost = std::numeric_limits::max() / 4 + 1; - } else { - art_cost = std::numeric_limits::min(); - for (int i = 0; i != _arc_num; ++i) { - if (_cost[i] > art_cost) art_cost = _cost[i]; - } - art_cost = (art_cost + 1) * _node_num; - } - // Remove non-zero lower bounds if (_plower) { for (int i = 0; i != _arc_num; ++i) { @@ -1118,14 +1290,14 @@ _cost[e] = art_cost; _cap[e] = inf_cap; _state[e] = STATE_TREE; - if (_supply[u] >= 0) { + if (_supply[u] > 0 || (_supply[u] == 0 && sum_supply <= 0)) { _flow[e] = _supply[u]; _forward[u] = true; - _pi[u] = -art_cost; + _pi[u] = -art_cost + _pi[_root]; } else { _flow[e] = -_supply[u]; _forward[u] = false; - _pi[u] = art_cost; + _pi[u] = art_cost + _pi[_root]; } } @@ -1382,11 +1554,6 @@ } } - // Check if the flow amount equals zero on all the artificial arcs - for (int e = _arc_num; e != _arc_num + _node_num; ++e) { - if (_flow[e] > 0) return false; - } - // Copy flow values to _flow_map if (_plower) { for (int i = 0; i != _arc_num; ++i) { diff --git a/test/min_cost_flow_test.cc b/test/min_cost_flow_test.cc --- a/test/min_cost_flow_test.cc +++ b/test/min_cost_flow_test.cc @@ -33,19 +33,19 @@ char test_lgf[] = "@nodes\n" - "label sup1 sup2 sup3\n" - " 1 20 27 0\n" - " 2 -4 0 0\n" - " 3 0 0 0\n" - " 4 0 0 0\n" - " 5 9 0 0\n" - " 6 -6 0 0\n" - " 7 0 0 0\n" - " 8 0 0 0\n" - " 9 3 0 0\n" - " 10 -2 0 0\n" - " 11 0 0 0\n" - " 12 -20 -27 0\n" + "label sup1 sup2 sup3 sup4 sup5\n" + " 1 20 27 0 20 30\n" + " 2 -4 0 0 -8 -3\n" + " 3 0 0 0 0 0\n" + " 4 0 0 0 0 0\n" + " 5 9 0 0 6 11\n" + " 6 -6 0 0 -5 -6\n" + " 7 0 0 0 0 0\n" + " 8 0 0 0 0 3\n" + " 9 3 0 0 0 0\n" + " 10 -2 0 0 -7 -2\n" + " 11 0 0 0 -10 0\n" + " 12 -20 -27 0 -30 -20\n" "\n" "@arcs\n" " cost cap low1 low2\n" @@ -76,6 +76,12 @@ "target 12\n"; +enum ProblemType { + EQ, + GEQ, + LEQ +}; + // Check the interface of an MCF algorithm template class McfClassConcept @@ -97,17 +103,19 @@ .costMap(cost) .supplyMap(sup) .stSupply(n, n, k) + .flowMap(flow) + .potentialMap(pot) .run(); + + const MCF& const_mcf = mcf; - const typename MCF::FlowMap &fm = mcf.flowMap(); - const typename MCF::PotentialMap &pm = mcf.potentialMap(); + const typename MCF::FlowMap &fm = const_mcf.flowMap(); + const typename MCF::PotentialMap &pm = const_mcf.potentialMap(); - v = mcf.totalCost(); - double x = mcf.template totalCost(); - v = mcf.flow(a); - v = mcf.potential(n); - mcf.flowMap(flow); - mcf.potentialMap(pot); + v = const_mcf.totalCost(); + double x = const_mcf.template totalCost(); + v = const_mcf.flow(a); + v = const_mcf.potential(n); ignore_unused_variable_warning(fm); ignore_unused_variable_warning(pm); @@ -142,7 +150,8 @@ template < typename GR, typename LM, typename UM, typename SM, typename FM > bool checkFlow( const GR& gr, const LM& lower, const UM& upper, - const SM& supply, const FM& flow ) + const SM& supply, const FM& flow, + ProblemType type = EQ ) { TEMPLATE_DIGRAPH_TYPEDEFS(GR); @@ -156,7 +165,10 @@ sum += flow[e]; for (InArcIt e(gr, n); e != INVALID; ++e) sum -= flow[e]; - if (sum != supply[n]) return false; + bool b = (type == EQ && sum == supply[n]) || + (type == GEQ && sum >= supply[n]) || + (type == LEQ && sum <= supply[n]); + if (!b) return false; } return true; @@ -165,9 +177,10 @@ // Check the feasibility of the given potentials (dual soluiton) // using the "Complementary Slackness" optimality condition template < typename GR, typename LM, typename UM, - typename CM, typename FM, typename PM > + typename CM, typename SM, typename FM, typename PM > bool checkPotential( const GR& gr, const LM& lower, const UM& upper, - const CM& cost, const FM& flow, const PM& pi ) + const CM& cost, const SM& supply, const FM& flow, + const PM& pi ) { TEMPLATE_DIGRAPH_TYPEDEFS(GR); @@ -179,6 +192,16 @@ (red_cost > 0 && flow[e] == lower[e]) || (red_cost < 0 && flow[e] == upper[e]); } + + for (NodeIt n(gr); opt && n != INVALID; ++n) { + typename SM::Value sum = 0; + for (OutArcIt e(gr, n); e != INVALID; ++e) + sum += flow[e]; + for (InArcIt e(gr, n); e != INVALID; ++e) + sum -= flow[e]; + opt = (sum == supply[n]) || (pi[n] == 0); + } + return opt; } @@ -190,14 +213,15 @@ const GR& gr, const LM& lower, const UM& upper, const CM& cost, const SM& supply, bool result, typename CM::Value total, - const std::string &test_id = "" ) + const std::string &test_id = "", + ProblemType type = EQ ) { check(mcf_result == result, "Wrong result " + test_id); if (result) { - check(checkFlow(gr, lower, upper, supply, mcf.flowMap()), + check(checkFlow(gr, lower, upper, supply, mcf.flowMap(), type), "The flow is not feasible " + test_id); check(mcf.totalCost() == total, "The flow is not optimal " + test_id); - check(checkPotential(gr, lower, upper, cost, mcf.flowMap(), + check(checkPotential(gr, lower, upper, cost, supply, mcf.flowMap(), mcf.potentialMap()), "Wrong potentials " + test_id); } @@ -226,7 +250,7 @@ // Read the test digraph Digraph gr; Digraph::ArcMap c(gr), l1(gr), l2(gr), u(gr); - Digraph::NodeMap s1(gr), s2(gr), s3(gr); + Digraph::NodeMap s1(gr), s2(gr), s3(gr), s4(gr), s5(gr); ConstMap cc(1), cu(std::numeric_limits::max()); Node v, w; @@ -239,6 +263,8 @@ .nodeMap("sup1", s1) .nodeMap("sup2", s2) .nodeMap("sup3", s3) + .nodeMap("sup4", s4) + .nodeMap("sup5", s5) .node("source", v) .node("target", w) .run(); @@ -247,6 +273,7 @@ { NetworkSimplex mcf(gr); + // Check the equality form mcf.upperMap(u).costMap(c); checkMcf(mcf, mcf.supplyMap(s1).run(), gr, l1, u, c, s1, true, 5240, "#A1"); @@ -267,6 +294,28 @@ gr, l1, cu, cc, s3, true, 0, "#A7"); checkMcf(mcf, mcf.boundMaps(l2, u).run(), gr, l2, u, cc, s3, false, 0, "#A8"); + + // Check the GEQ form + mcf.reset().upperMap(u).costMap(c).supplyMap(s4); + checkMcf(mcf, mcf.run(), + gr, l1, u, c, s4, true, 3530, "#A9", GEQ); + mcf.problemType(mcf.GEQ); + checkMcf(mcf, mcf.lowerMap(l2).run(), + gr, l2, u, c, s4, true, 4540, "#A10", GEQ); + mcf.problemType(mcf.CARRY_SUPPLIES).supplyMap(s5); + checkMcf(mcf, mcf.run(), + gr, l2, u, c, s5, false, 0, "#A11", GEQ); + + // Check the LEQ form + mcf.reset().problemType(mcf.LEQ); + mcf.upperMap(u).costMap(c).supplyMap(s5); + checkMcf(mcf, mcf.run(), + gr, l1, u, c, s5, true, 5080, "#A12", LEQ); + checkMcf(mcf, mcf.lowerMap(l2).run(), + gr, l2, u, c, s5, true, 5930, "#A13", LEQ); + mcf.problemType(mcf.SATISFY_DEMANDS).supplyMap(s4); + checkMcf(mcf, mcf.run(), + gr, l2, u, c, s4, false, 0, "#A14", LEQ); } // B. Test NetworkSimplex with each pivot rule