COIN-OR::LEMON - Graph Library

Changeset 609:e6927fe719e6 in lemon-1.2 for test/min_cost_flow_test.cc


Ignore:
Timestamp:
04/17/09 18:04:36 (11 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:
1 edited

Legend:

Unmodified
Added
Removed
  • test/min_cost_flow_test.cc

    r607 r609  
    3434char test_lgf[] =
    3535  "@nodes\n"
    36   "label  sup1 sup2 sup3\n"
    37   "    1    20   27    0\n"
    38   "    2    -4    0    0\n"
    39   "    3     0    0    0\n"
    40   "    4     0    0    0\n"
    41   "    5     9    0    0\n"
    42   "    6    -6    0    0\n"
    43   "    7     0    0    0\n"
    44   "    8     0    0    0\n"
    45   "    9     3    0    0\n"
    46   "   10    -2    0    0\n"
    47   "   11     0    0    0\n"
    48   "   12   -20  -27    0\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"
    4949  "\n"
    5050  "@arcs\n"
     
    7777
    7878
     79enum ProblemType {
     80  EQ,
     81  GEQ,
     82  LEQ
     83};
     84
    7985// Check the interface of an MCF algorithm
    8086template <typename GR, typename Flow, typename Cost>
     
    98104             .supplyMap(sup)
    99105             .stSupply(n, n, k)
     106             .flowMap(flow)
     107             .potentialMap(pot)
    100108             .run();
    101 
    102       const typename MCF::FlowMap &fm = mcf.flowMap();
    103       const typename MCF::PotentialMap &pm = mcf.potentialMap();
    104 
    105       v = mcf.totalCost();
    106       double x = mcf.template totalCost<double>();
    107       v = mcf.flow(a);
    108       v = mcf.potential(n);
    109       mcf.flowMap(flow);
    110       mcf.potentialMap(pot);
     109     
     110      const MCF& const_mcf = mcf;
     111
     112      const typename MCF::FlowMap &fm = const_mcf.flowMap();
     113      const typename MCF::PotentialMap &pm = const_mcf.potentialMap();
     114
     115      v = const_mcf.totalCost();
     116      double x = const_mcf.template totalCost<double>();
     117      v = const_mcf.flow(a);
     118      v = const_mcf.potential(n);
    111119
    112120      ignore_unused_variable_warning(fm);
     
    143151           typename SM, typename FM >
    144152bool checkFlow( const GR& gr, const LM& lower, const UM& upper,
    145                 const SM& supply, const FM& flow )
     153                const SM& supply, const FM& flow,
     154                ProblemType type = EQ )
    146155{
    147156  TEMPLATE_DIGRAPH_TYPEDEFS(GR);
     
    157166    for (InArcIt e(gr, n); e != INVALID; ++e)
    158167      sum -= flow[e];
    159     if (sum != supply[n]) return false;
     168    bool b = (type ==  EQ && sum == supply[n]) ||
     169             (type == GEQ && sum >= supply[n]) ||
     170             (type == LEQ && sum <= supply[n]);
     171    if (!b) return false;
    160172  }
    161173
     
    166178// using the "Complementary Slackness" optimality condition
    167179template < typename GR, typename LM, typename UM,
    168            typename CM, typename FM, typename PM >
     180           typename CM, typename SM, typename FM, typename PM >
    169181bool checkPotential( const GR& gr, const LM& lower, const UM& upper,
    170                      const CM& cost, const FM& flow, const PM& pi )
     182                     const CM& cost, const SM& supply, const FM& flow,
     183                     const PM& pi )
    171184{
    172185  TEMPLATE_DIGRAPH_TYPEDEFS(GR);
     
    180193          (red_cost < 0 && flow[e] == upper[e]);
    181194  }
     195 
     196  for (NodeIt n(gr); opt && n != INVALID; ++n) {
     197    typename SM::Value sum = 0;
     198    for (OutArcIt e(gr, n); e != INVALID; ++e)
     199      sum += flow[e];
     200    for (InArcIt e(gr, n); e != INVALID; ++e)
     201      sum -= flow[e];
     202    opt = (sum == supply[n]) || (pi[n] == 0);
     203  }
     204 
    182205  return opt;
    183206}
     
    191214               const CM& cost, const SM& supply,
    192215               bool result, typename CM::Value total,
    193                const std::string &test_id = "" )
     216               const std::string &test_id = "",
     217               ProblemType type = EQ )
    194218{
    195219  check(mcf_result == result, "Wrong result " + test_id);
    196220  if (result) {
    197     check(checkFlow(gr, lower, upper, supply, mcf.flowMap()),
     221    check(checkFlow(gr, lower, upper, supply, mcf.flowMap(), type),
    198222          "The flow is not feasible " + test_id);
    199223    check(mcf.totalCost() == total, "The flow is not optimal " + test_id);
    200     check(checkPotential(gr, lower, upper, cost, mcf.flowMap(),
     224    check(checkPotential(gr, lower, upper, cost, supply, mcf.flowMap(),
    201225                         mcf.potentialMap()),
    202226          "Wrong potentials " + test_id);
     
    227251  Digraph gr;
    228252  Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), u(gr);
    229   Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr);
     253  Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr);
    230254  ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());
    231255  Node v, w;
     
    240264    .nodeMap("sup2", s2)
    241265    .nodeMap("sup3", s3)
     266    .nodeMap("sup4", s4)
     267    .nodeMap("sup5", s5)
    242268    .node("source", v)
    243269    .node("target", w)
     
    248274    NetworkSimplex<Digraph> mcf(gr);
    249275
     276    // Check the equality form
    250277    mcf.upperMap(u).costMap(c);
    251278    checkMcf(mcf, mcf.supplyMap(s1).run(),
     
    268295    checkMcf(mcf, mcf.boundMaps(l2, u).run(),
    269296             gr, l2, u, cc, s3, false,   0, "#A8");
     297
     298    // Check the GEQ form
     299    mcf.reset().upperMap(u).costMap(c).supplyMap(s4);
     300    checkMcf(mcf, mcf.run(),
     301             gr, l1, u, c, s4, true,  3530, "#A9", GEQ);
     302    mcf.problemType(mcf.GEQ);
     303    checkMcf(mcf, mcf.lowerMap(l2).run(),
     304             gr, l2, u, c, s4, true,  4540, "#A10", GEQ);
     305    mcf.problemType(mcf.CARRY_SUPPLIES).supplyMap(s5);
     306    checkMcf(mcf, mcf.run(),
     307             gr, l2, u, c, s5, false,    0, "#A11", GEQ);
     308
     309    // Check the LEQ form
     310    mcf.reset().problemType(mcf.LEQ);
     311    mcf.upperMap(u).costMap(c).supplyMap(s5);
     312    checkMcf(mcf, mcf.run(),
     313             gr, l1, u, c, s5, true,  5080, "#A12", LEQ);
     314    checkMcf(mcf, mcf.lowerMap(l2).run(),
     315             gr, l2, u, c, s5, true,  5930, "#A13", LEQ);
     316    mcf.problemType(mcf.SATISFY_DEMANDS).supplyMap(s4);
     317    checkMcf(mcf, mcf.run(),
     318             gr, l2, u, c, s4, false,    0, "#A14", LEQ);
    270319  }
    271320
Note: See TracChangeset for help on using the changeset viewer.