Changeset 656:e6927fe719e6 in lemon for test/min_cost_flow_test.cc

Timestamp:

04/17/09 18:04:36 (15 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Support >= and <= constraints in NetworkSimplex? (#219, #234)

By default the same inequality constraints are supported as by
Circulation (the GEQ form), but the LEQ form can also be selected
using the problemType() function.

The documentation of the min. cost flow module is reworked and
extended with important notes and explanations about the different
variants of the problem and about the dual solution and optimality
conditions.

File:

• test/min_cost_flow_test.cc (modified) (12 diffs)

test/min_cost_flow_test.cc

@@ -34 +34 @@
 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"
@@ -77 +77 @@
 
 
+enum ProblemType {
+  EQ,
+  GEQ,
+  LEQ
+};
+
 // Check the interface of an MCF algorithm
 template <typename GR, typename Flow, typename Cost>
@@ -98 +104 @@
              .supplyMap(sup)
              .stSupply(n, n, k)
+             .flowMap(flow)
+             .potentialMap(pot)
              .run();
-
-      const typename MCF::FlowMap &fm = mcf.flowMap();
-      const typename MCF::PotentialMap &pm = mcf.potentialMap();
-
-      v = mcf.totalCost();
-      double x = mcf.template totalCost<double>();
-      v = mcf.flow(a);
-      v = mcf.potential(n);
-      mcf.flowMap(flow);
-      mcf.potentialMap(pot);
+      
+      const MCF& const_mcf = mcf;
+
+      const typename MCF::FlowMap &fm = const_mcf.flowMap();
+      const typename MCF::PotentialMap &pm = const_mcf.potentialMap();
+
+      v = const_mcf.totalCost();
+      double x = const_mcf.template totalCost<double>();
+      v = const_mcf.flow(a);
+      v = const_mcf.potential(n);
 
       ignore_unused_variable_warning(fm);
@@ -143 +151 @@
            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);
@@ -157 +166 @@
     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;
   }
 
@@ -166 +178 @@
 // 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);
@@ -180 +193 @@
           (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;
 }
@@ -191 +214 @@
                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);
@@ -227 +251 @@
   Digraph gr;
   Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), u(gr);
-  Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr);
+  Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr);
   ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());
   Node v, w;
@@ -240 +264 @@
     .nodeMap("sup2", s2)
     .nodeMap("sup3", s3)
+    .nodeMap("sup4", s4)
+    .nodeMap("sup5", s5)
     .node("source", v)
     .node("target", w)
@@ -248 +274 @@
     NetworkSimplex<Digraph> mcf(gr);
 
+    // Check the equality form
     mcf.upperMap(u).costMap(c);
     checkMcf(mcf, mcf.supplyMap(s1).run(),
@@ -268 +295 @@
     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);
   }