COIN-OR::LEMON - Graph Library

Ignore:
Timestamp:
04/29/09 03:15:24 (15 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Support negative costs and bounds in NetworkSimplex? (#270)

  • The interface is reworked to support negative costs and bounds.
    • ProblemType? and problemType() are renamed to SupplyType? and supplyType(), see also #234.
    • ProblemType? type is introduced similarly to the LP interface.
    • 'bool run()' is replaced by 'ProblemType? run()' to handle unbounded problem instances, as well.
    • Add INF public member constant similarly to the LP interface.
  • Remove capacityMap() and boundMaps(), see also #266.
  • Update the problem definition in the MCF module.
  • Remove the usage of Circulation (and adaptors) for checking feasibility. Check feasibility by examining the artifical arcs instead (after solving the problem).
  • Additional check for unbounded negative cycles found during the algorithm (it is possible now, since negative costs are allowed).
  • Fix in the constructor (the value types needn't be integer any more), see also #254.
  • Improve and extend the doc.
  • Rework the test file and add test cases for negative costs and bounds.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • test/min_cost_flow_test.cc

    r662 r687  
    1919#include <iostream>
    2020#include <fstream>
     21#include <limits>
    2122
    2223#include <lemon/list_graph.h>
     
    3435char test_lgf[] =
    3536  "@nodes\n"
    36   "label  sup1 sup2 sup3 sup4 sup5\n"
    37   "    1    20   27    0   20   30\n"
    38   "    2    -4    0    0   -8   -3\n"
    39   "    3     0    0    0    0    0\n"
    40   "    4     0    0    0    0    0\n"
    41   "    5     9    0    0    6   11\n"
    42   "    6    -6    0    0   -5   -6\n"
    43   "    7     0    0    0    0    0\n"
    44   "    8     0    0    0    0    3\n"
    45   "    9     3    0    0    0    0\n"
    46   "   10    -2    0    0   -7   -2\n"
    47   "   11     0    0    0  -10    0\n"
    48   "   12   -20  -27    0  -30  -20\n"
    49   "\n"
     37  "label  sup1 sup2 sup3 sup4 sup5 sup6\n"
     38  "    1    20   27    0   30   20   30\n"
     39  "    2    -4    0    0    0   -8   -3\n"
     40  "    3     0    0    0    0    0    0\n"
     41  "    4     0    0    0    0    0    0\n"
     42  "    5     9    0    0    0    6   11\n"
     43  "    6    -6    0    0    0   -5   -6\n"
     44  "    7     0    0    0    0    0    0\n"
     45  "    8     0    0    0    0    0    3\n"
     46  "    9     3    0    0    0    0    0\n"
     47  "   10    -2    0    0    0   -7   -2\n"
     48  "   11     0    0    0    0  -10    0\n"
     49  "   12   -20  -27    0  -30  -30  -20\n"
     50  "\n"               
    5051  "@arcs\n"
    51   "       cost  cap low1 low2\n"
    52   " 1  2    70   11    0    8\n"
    53   " 1  3   150    3    0    1\n"
    54   " 1  4    80   15    0    2\n"
    55   " 2  8    80   12    0    0\n"
    56   " 3  5   140    5    0    3\n"
    57   " 4  6    60   10    0    1\n"
    58   " 4  7    80    2    0    0\n"
    59   " 4  8   110    3    0    0\n"
    60   " 5  7    60   14    0    0\n"
    61   " 5 11   120   12    0    0\n"
    62   " 6  3     0    3    0    0\n"
    63   " 6  9   140    4    0    0\n"
    64   " 6 10    90    8    0    0\n"
    65   " 7  1    30    5    0    0\n"
    66   " 8 12    60   16    0    4\n"
    67   " 9 12    50    6    0    0\n"
    68   "10 12    70   13    0    5\n"
    69   "10  2   100    7    0    0\n"
    70   "10  7    60   10    0    0\n"
    71   "11 10    20   14    0    6\n"
    72   "12 11    30   10    0    0\n"
     52  "       cost  cap low1 low2 low3\n"
     53  " 1  2    70   11    0    8    8\n"
     54  " 1  3   150    3    0    1    0\n"
     55  " 1  4    80   15    0    2    2\n"
     56  " 2  8    80   12    0    0    0\n"
     57  " 3  5   140    5    0    3    1\n"
     58  " 4  6    60   10    0    1    0\n"
     59  " 4  7    80    2    0    0    0\n"
     60  " 4  8   110    3    0    0    0\n"
     61  " 5  7    60   14    0    0    0\n"
     62  " 5 11   120   12    0    0    0\n"
     63  " 6  3     0    3    0    0    0\n"
     64  " 6  9   140    4    0    0    0\n"
     65  " 6 10    90    8    0    0    0\n"
     66  " 7  1    30    5    0    0   -5\n"
     67  " 8 12    60   16    0    4    3\n"
     68  " 9 12    50    6    0    0    0\n"
     69  "10 12    70   13    0    5    2\n"
     70  "10  2   100    7    0    0    0\n"
     71  "10  7    60   10    0    0   -3\n"
     72  "11 10    20   14    0    6  -20\n"
     73  "12 11    30   10    0    0  -10\n"
    7374  "\n"
    7475  "@attributes\n"
     
    7778
    7879
    79 enum ProblemType {
     80enum SupplyType {
    8081  EQ,
    8182  GEQ,
     
    99100             .lowerMap(lower)
    100101             .upperMap(upper)
    101              .capacityMap(upper)
    102              .boundMaps(lower, upper)
    103102             .costMap(cost)
    104103             .supplyMap(sup)
     
    113112      const typename MCF::PotentialMap &pm = const_mcf.potentialMap();
    114113
    115       v = const_mcf.totalCost();
     114      c = const_mcf.totalCost();
    116115      double x = const_mcf.template totalCost<double>();
    117116      v = const_mcf.flow(a);
    118       v = const_mcf.potential(n);
     117      c = const_mcf.potential(n);
     118     
     119      v = const_mcf.INF;
    119120
    120121      ignore_unused_variable_warning(fm);
     
    138139    const Flow &k;
    139140    Flow v;
     141    Cost c;
    140142    bool b;
    141143
     
    152154bool checkFlow( const GR& gr, const LM& lower, const UM& upper,
    153155                const SM& supply, const FM& flow,
    154                 ProblemType type = EQ )
     156                SupplyType type = EQ )
    155157{
    156158  TEMPLATE_DIGRAPH_TYPEDEFS(GR);
     
    209211template < typename MCF, typename GR,
    210212           typename LM, typename UM,
    211            typename CM, typename SM >
    212 void checkMcf( const MCF& mcf, bool mcf_result,
     213           typename CM, typename SM,
     214           typename PT >
     215void checkMcf( const MCF& mcf, PT mcf_result,
    213216               const GR& gr, const LM& lower, const UM& upper,
    214217               const CM& cost, const SM& supply,
    215                bool result, typename CM::Value total,
     218               PT result, bool optimal, typename CM::Value total,
    216219               const std::string &test_id = "",
    217                ProblemType type = EQ )
     220               SupplyType type = EQ )
    218221{
    219222  check(mcf_result == result, "Wrong result " + test_id);
    220   if (result) {
     223  if (optimal) {
    221224    check(checkFlow(gr, lower, upper, supply, mcf.flowMap(), type),
    222225          "The flow is not feasible " + test_id);
     
    245248  // Read the test digraph
    246249  Digraph gr;
    247   Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), u(gr);
    248   Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr);
     250  Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), l3(gr), u(gr);
     251  Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr), s6(gr);
    249252  ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());
    250253  Node v, w;
     
    256259    .arcMap("low1", l1)
    257260    .arcMap("low2", l2)
     261    .arcMap("low3", l3)
    258262    .nodeMap("sup1", s1)
    259263    .nodeMap("sup2", s2)
     
    261265    .nodeMap("sup4", s4)
    262266    .nodeMap("sup5", s5)
     267    .nodeMap("sup6", s6)
    263268    .node("source", v)
    264269    .node("target", w)
    265270    .run();
     271 
     272  // Build a test digraph for testing negative costs
     273  Digraph ngr;
     274  Node n1 = ngr.addNode();
     275  Node n2 = ngr.addNode();
     276  Node n3 = ngr.addNode();
     277  Node n4 = ngr.addNode();
     278  Node n5 = ngr.addNode();
     279  Node n6 = ngr.addNode();
     280  Node n7 = ngr.addNode();
     281 
     282  Arc a1 = ngr.addArc(n1, n2);
     283  Arc a2 = ngr.addArc(n1, n3);
     284  Arc a3 = ngr.addArc(n2, n4);
     285  Arc a4 = ngr.addArc(n3, n4);
     286  Arc a5 = ngr.addArc(n3, n2);
     287  Arc a6 = ngr.addArc(n5, n3);
     288  Arc a7 = ngr.addArc(n5, n6);
     289  Arc a8 = ngr.addArc(n6, n7);
     290  Arc a9 = ngr.addArc(n7, n5);
     291 
     292  Digraph::ArcMap<int> nc(ngr), nl1(ngr, 0), nl2(ngr, 0);
     293  ConstMap<Arc, int> nu1(std::numeric_limits<int>::max()), nu2(5000);
     294  Digraph::NodeMap<int> ns(ngr, 0);
     295 
     296  nl2[a7] =  1000;
     297  nl2[a8] = -1000;
     298 
     299  ns[n1] =  100;
     300  ns[n4] = -100;
     301 
     302  nc[a1] =  100;
     303  nc[a2] =   30;
     304  nc[a3] =   20;
     305  nc[a4] =   80;
     306  nc[a5] =   50;
     307  nc[a6] =   10;
     308  nc[a7] =   80;
     309  nc[a8] =   30;
     310  nc[a9] = -120;
    266311
    267312  // A. Test NetworkSimplex with the default pivot rule
     
    272317    mcf.upperMap(u).costMap(c);
    273318    checkMcf(mcf, mcf.supplyMap(s1).run(),
    274              gr, l1, u, c, s1, true,  5240, "#A1");
     319             gr, l1, u, c, s1, mcf.OPTIMAL, true,   5240, "#A1");
    275320    checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
    276              gr, l1, u, c, s2, true,  7620, "#A2");
     321             gr, l1, u, c, s2, mcf.OPTIMAL, true,   7620, "#A2");
    277322    mcf.lowerMap(l2);
    278323    checkMcf(mcf, mcf.supplyMap(s1).run(),
    279              gr, l2, u, c, s1, true,  5970, "#A3");
     324             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#A3");
    280325    checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
    281              gr, l2, u, c, s2, true,  8010, "#A4");
     326             gr, l2, u, c, s2, mcf.OPTIMAL, true,   8010, "#A4");
    282327    mcf.reset();
    283328    checkMcf(mcf, mcf.supplyMap(s1).run(),
    284              gr, l1, cu, cc, s1, true,  74, "#A5");
     329             gr, l1, cu, cc, s1, mcf.OPTIMAL, true,   74, "#A5");
    285330    checkMcf(mcf, mcf.lowerMap(l2).stSupply(v, w, 27).run(),
    286              gr, l2, cu, cc, s2, true,  94, "#A6");
     331             gr, l2, cu, cc, s2, mcf.OPTIMAL, true,   94, "#A6");
    287332    mcf.reset();
    288333    checkMcf(mcf, mcf.run(),
    289              gr, l1, cu, cc, s3, true,   0, "#A7");
    290     checkMcf(mcf, mcf.boundMaps(l2, u).run(),
    291              gr, l2, u, cc, s3, false,   0, "#A8");
     334             gr, l1, cu, cc, s3, mcf.OPTIMAL, true,    0, "#A7");
     335    checkMcf(mcf, mcf.lowerMap(l2).upperMap(u).run(),
     336             gr, l2, u, cc, s3, mcf.INFEASIBLE, false, 0, "#A8");
     337    mcf.reset().lowerMap(l3).upperMap(u).costMap(c).supplyMap(s4);
     338    checkMcf(mcf, mcf.run(),
     339             gr, l3, u, c, s4, mcf.OPTIMAL, true,   6360, "#A9");
    292340
    293341    // Check the GEQ form
    294     mcf.reset().upperMap(u).costMap(c).supplyMap(s4);
    295     checkMcf(mcf, mcf.run(),
    296              gr, l1, u, c, s4, true,  3530, "#A9", GEQ);
    297     mcf.problemType(mcf.GEQ);
     342    mcf.reset().upperMap(u).costMap(c).supplyMap(s5);
     343    checkMcf(mcf, mcf.run(),
     344             gr, l1, u, c, s5, mcf.OPTIMAL, true,   3530, "#A10", GEQ);
     345    mcf.supplyType(mcf.GEQ);
    298346    checkMcf(mcf, mcf.lowerMap(l2).run(),
    299              gr, l2, u, c, s4, true,  4540, "#A10", GEQ);
    300     mcf.problemType(mcf.CARRY_SUPPLIES).supplyMap(s5);
    301     checkMcf(mcf, mcf.run(),
    302              gr, l2, u, c, s5, false,    0, "#A11", GEQ);
     347             gr, l2, u, c, s5, mcf.OPTIMAL, true,   4540, "#A11", GEQ);
     348    mcf.supplyType(mcf.CARRY_SUPPLIES).supplyMap(s6);
     349    checkMcf(mcf, mcf.run(),
     350             gr, l2, u, c, s6, mcf.INFEASIBLE, false,  0, "#A12", GEQ);
    303351
    304352    // Check the LEQ form
    305     mcf.reset().problemType(mcf.LEQ);
    306     mcf.upperMap(u).costMap(c).supplyMap(s5);
    307     checkMcf(mcf, mcf.run(),
    308              gr, l1, u, c, s5, true,  5080, "#A12", LEQ);
     353    mcf.reset().supplyType(mcf.LEQ);
     354    mcf.upperMap(u).costMap(c).supplyMap(s6);
     355    checkMcf(mcf, mcf.run(),
     356             gr, l1, u, c, s6, mcf.OPTIMAL, true,   5080, "#A13", LEQ);
    309357    checkMcf(mcf, mcf.lowerMap(l2).run(),
    310              gr, l2, u, c, s5, true,  5930, "#A13", LEQ);
    311     mcf.problemType(mcf.SATISFY_DEMANDS).supplyMap(s4);
    312     checkMcf(mcf, mcf.run(),
    313              gr, l2, u, c, s4, false,    0, "#A14", LEQ);
     358             gr, l2, u, c, s6, mcf.OPTIMAL, true,   5930, "#A14", LEQ);
     359    mcf.supplyType(mcf.SATISFY_DEMANDS).supplyMap(s5);
     360    checkMcf(mcf, mcf.run(),
     361             gr, l2, u, c, s5, mcf.INFEASIBLE, false,  0, "#A15", LEQ);
     362
     363    // Check negative costs
     364    NetworkSimplex<Digraph> nmcf(ngr);
     365    nmcf.lowerMap(nl1).costMap(nc).supplyMap(ns);
     366    checkMcf(nmcf, nmcf.run(),
     367      ngr, nl1, nu1, nc, ns, nmcf.UNBOUNDED, false,    0, "#A16");
     368    checkMcf(nmcf, nmcf.upperMap(nu2).run(),
     369      ngr, nl1, nu2, nc, ns, nmcf.OPTIMAL, true,  -40000, "#A17");
     370    nmcf.reset().lowerMap(nl2).costMap(nc).supplyMap(ns);
     371    checkMcf(nmcf, nmcf.run(),
     372      ngr, nl2, nu1, nc, ns, nmcf.UNBOUNDED, false,    0, "#A18");
    314373  }
    315374
     
    317376  {
    318377    NetworkSimplex<Digraph> mcf(gr);
    319     mcf.supplyMap(s1).costMap(c).capacityMap(u).lowerMap(l2);
     378    mcf.supplyMap(s1).costMap(c).upperMap(u).lowerMap(l2);
    320379
    321380    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::FIRST_ELIGIBLE),
    322              gr, l2, u, c, s1, true,  5970, "#B1");
     381             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B1");
    323382    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BEST_ELIGIBLE),
    324              gr, l2, u, c, s1, true,  5970, "#B2");
     383             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B2");
    325384    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BLOCK_SEARCH),
    326              gr, l2, u, c, s1, true,  5970, "#B3");
     385             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B3");
    327386    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::CANDIDATE_LIST),
    328              gr, l2, u, c, s1, true,  5970, "#B4");
     387             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B4");
    329388    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::ALTERING_LIST),
    330              gr, l2, u, c, s1, true,  5970, "#B5");
     389             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B5");
    331390  }
    332391
Note: See TracChangeset for help on using the changeset viewer.