I am using the new API in <a href="http://lemon.cs.elte.hu/trac/lemon/ticket/375">http://lemon.cs.elte.hu/trac/lemon/ticket/375</a>, which allows <=, >= constraints.<br><br>The following problem<br>int    nNodes       = 4;<br>

int    nArcs        = 4;<br>double supply_lo[4] = {0,-INF,0,22};<br>double supply_up[4] = {INF,-40,INF,INF};<br>int    source[4]   = {3,0,1,2};<br>int    target[4]   = {0,1,2,3};<br>double lower [4]   = {1689.96,1721.97,1667.97,1702.96};<br>

double upper [4]   = {INF,INF,INF,INF};<br>double cost  [4]   = {0.206,0.101,-0.099,-0.204};<br><br>This is equivalent to the linear programming problem:<br> var x0 >= 1689.96;<br> var x1 >= 1721.97;<br> var x2 >= 1667.97;<br>

 var x3 >= 1702.96;<br> min obj = 0.206 * x0 + 0.101 * x1 + -0.099 * x2 + -0.204 * x3;<br> con con0:  -x0 + x1 >=  0;<br> con con1:  -x1 + x2 <=  -40;<br> con con2:  -x2 + x3 >=  0;<br> con con3:   x0 - x3 >=  22;<br>

<br>Which should have an optimal solution = 15.34784.<br>x[3,0]=1725<br>x[0,1]=1725<br>x[1,2]=1685<br>x[2,3]=1703<br><br>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?<br>

<br>The test program I used for this is below:<br><br>//===========================================================================<br>#include <vector><br>#include <fstream><br>#include <lemon/dimacs.h><br>

#include <lemon/smart_graph.h><br>#include <lemon/network_simplex.h><br><br>//===========================================================================<br>using namespace std;<br>using namespace lemon;<br>typedef SmartDigraph Digraph;<br>

DIGRAPH_TYPEDEFS(Digraph);<br>#define INF 1e+20<br><br>//===========================================================================<br>//Example 2 (comp 138)<br>int    nNodes       = 4;<br>int    nArcs        = 4;<br>double supply_lo[4] = {0,-INF,0,22};<br>

double supply_up[4] = {INF,-40,INF,INF};<br>int    source[4]   = {3,0,1,2};<br>int    target[4]   = {0,1,2,3};<br>double lower [4]   = {1689.96,1721.97,1667.97,1702.96};<br>double upper [4]   = {INF,INF,INF,INF};<br>double cost  [4]   = {0.206,0.101,-0.099,-0.204};<br>

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

<br>   int i;<br>   vector<Digraph::Node> nodes(nNodes);<br>   for(i = nNodes-1; i >=0; i--){<br>      nodes[i] = g.addNode();<br>      supplyLoMap.set(nodes[i], supply_lo[i]);<br>      supplyUpMap.set(nodes[i], supply_up[i]);<br>

   }<br>   Digraph::Arc e;<br>   for(i = nArcs-1; i >= 0; i--){<br>      e = g.addArc(nodes[source[i]], nodes[target[i]]);<br>      lowerMap.set(e, lower[i]);<br>      upperMap.set(e, upper[i]);<br>      costMap.set (e, cost[i]);<br>

   }<br>   printf("nodeNum=%d arcNum=%d\n", g.nodeNum(), g.arcNum());<br>   ofstream os("tmp.txt");<br>   writeDimacsMat(os,g);<br><br>   NetworkSimplex<Digraph, double> ns(g);<br>   ns.lowerMap(lowerMap).upperMap(upperMap).costMap(costMap);<br>

   ns.supplyBounds(supplyLoMap,supplyUpMap);<br><br>   bool res = ns.run();   <br>   cout << "Feasible flow: " <br>        << (res ? "found" : "not found") << endl;<br>   if (res) std::cerr << "Min flow cost: "<br>

                      << ns.totalCost() << '\n';<br>   return 0;<br>}<br><br><br><br>