[Lemon-user] error in min-cost network flow example

[Matthew Galati]

I am using the new API in http://lemon.cs.elte.hu/trac/lemon/ticket/375,
which allows <=, >= constraints.

The following problem
int    nNodes       = 4;
int    nArcs        = 4;
double supply_lo[4] = {0,-INF,0,22};
double supply_up[4] = {INF,-40,INF,INF};
int    source[4]   = {3,0,1,2};
int    target[4]   = {0,1,2,3};
double lower [4]   = {1689.96,1721.97,1667.97,1702.96};
double upper [4]   = {INF,INF,INF,INF};
double cost  [4]   = {0.206,0.101,-0.099,-0.204};

This is equivalent to the linear programming problem:
 var x0 >= 1689.96;
 var x1 >= 1721.97;
 var x2 >= 1667.97;
 var x3 >= 1702.96;
 min obj = 0.206 * x0 + 0.101 * x1 + -0.099 * x2 + -0.204 * x3;
 con con0:  -x0 + x1 >=  0;
 con con1:  -x1 + x2 <=  -40;
 con con2:  -x2 + x3 >=  0;
 con con3:   x0 - x3 >=  22;

Which should have an optimal solution = 15.34784.
x[3,0]=1725
x[0,1]=1725
x[1,2]=1685
x[2,3]=1703

However, the network simplex solver is declaring the optimal obj = 20.7679.
Can you please tell me if there is a bug in the solver or if I am using it
wrong?

The test program I used for this is below:

//===========================================================================
#include <vector>
#include <fstream>
#include <lemon/dimacs.h>
#include <lemon/smart_graph.h>
#include <lemon/network_simplex.h>

//===========================================================================
using namespace std;
using namespace lemon;
typedef SmartDigraph Digraph;
DIGRAPH_TYPEDEFS(Digraph);
#define INF 1e+20

//===========================================================================
//Example 2 (comp 138)
int    nNodes       = 4;
int    nArcs        = 4;
double supply_lo[4] = {0,-INF,0,22};
double supply_up[4] = {INF,-40,INF,INF};
int    source[4]   = {3,0,1,2};
int    target[4]   = {0,1,2,3};
double lower [4]   = {1689.96,1721.97,1667.97,1702.96};
double upper [4]   = {INF,INF,INF,INF};
double cost  [4]   = {0.206,0.101,-0.099,-0.204};


//===========================================================================
int main(int argc, char ** argv){
   Digraph g;
   Digraph::ArcMap<double>  lowerMap(g), upperMap(g), costMap(g);
   Digraph::NodeMap<double> supplyLoMap(g), supplyUpMap(g);

   int i;
   vector<Digraph::Node> nodes(nNodes);
   for(i = nNodes-1; i >=0; i--){
      nodes[i] = g.addNode();
      supplyLoMap.set(nodes[i], supply_lo[i]);
      supplyUpMap.set(nodes[i], supply_up[i]);
   }
   Digraph::Arc e;
   for(i = nArcs-1; i >= 0; i--){
      e = g.addArc(nodes[source[i]], nodes[target[i]]);
      lowerMap.set(e, lower[i]);
      upperMap.set(e, upper[i]);
      costMap.set (e, cost[i]);
   }
   printf("nodeNum=%d arcNum=%d\n", g.nodeNum(), g.arcNum());
   ofstream os("tmp.txt");
   writeDimacsMat(os,g);

   NetworkSimplex<Digraph, double> ns(g);
   ns.lowerMap(lowerMap).upperMap(upperMap).costMap(costMap);
   ns.supplyBounds(supplyLoMap,supplyUpMap);

   bool res = ns.run();
   cout << "Feasible flow: "
        << (res ? "found" : "not found") << endl;
   if (res) std::cerr << "Min flow cost: "
                      << ns.totalCost() << '\n';
   return 0;
}
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20100803/32135aa1/attachment.html>