Support infinite and negative data in NetworkSimplex

[Peter Kovacs]

It would be nice to support infinte capacities (upper bounds), negative lower and upper bounds and negative costs in NetworkSimplex (and in Circulation as well).

[Peter Kovacs]

[547e6b876ee1] solves this issue for Circulation and fixes the doc (lower and upper bounds can be negative). In fact, it required moderate changes.

[Peter Kovacs]

In NetworkSimplex I suggest the following changes in the interface:

• Rename ProblemType to SupplyType (or SupplyConstraint).
• Rename problemType() to supplyType() (or supplyConstraint()).
• Add a new public type similarly to the Lp interface:

  enum ProblemType {
    INFEASIBLE,
    OPTIMAL,
    UNBOUNDED
  }
  

• Replace bool run() with ProblemType run().

Negative costs and negative lower/upper bounds have to be supported as well as positive infinity upper bounds. However negative infinity lower bounds could be disregarded or postponed.

[Peter Kovacs]

I forgot something: a public value INF should also be introduced to obtain the infinity Flow value.

[Alpar Juttner]

Replying to kpeter:

[547e6b876ee1] solves this issue for Circulation and fixes the doc (lower and upper bounds can be negative). In fact, it required moderate changes.

[547e6b876ee1] doesn't compiles for me:

	g++ -DHAVE_CONFIG_H   -I. -I.  -Wall -W -Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas -g -O2 -MT test/circulation_test.o -MD -MP -MF $depbase.Tpo -c -o test/circulation_test.o test/circulation_test.cc &&\
	mv -f $depbase.Tpo $depbase.Po
In file included from test/circulation_test.cc:23:
./lemon/circulation.h: In member function 'bool lemon::Circulation<GR, LM, UM, SM, TR>::checkBarrier() const':
./lemon/circulation.h:751: error: 'numeric_limits' is not a member of 'std'
./lemon/circulation.h:751: error: expected primary-expression before '>' token
./lemon/circulation.h:751: error: '::has_infinity' has not been declared
./lemon/circulation.h:752: error: 'numeric_limits' is not a member of 'std'
./lemon/circulation.h:752: error: expected primary-expression before '>' token
./lemon/circulation.h:752: error: '::infinity' has not been declared
./lemon/circulation.h:753: error: 'numeric_limits' is not a member of 'std'
./lemon/circulation.h:753: error: expected primary-expression before '>' token
./lemon/circulation.h:753: error: '::max' has not been declared

[Peter Kovacs]

Replying to alpar:

[547e6b876ee1] doesn't compiles for me:

Strange, it worked for me. The problem was a missing #include <limits>.

[28f58740b6f8] is the fixed patch, wich is indeed merged with [c20b7ed31aad], see #266.

[Peter Kovacs]

There is outstanding issue of reworking the NetworkSimplex interface.

[Peter Kovacs]

Replying to kpeter:

There is outstanding issue of reworking the NetworkSimplex interface.

The attached patch [6c408d864fa1] solves this issue. Please check it (at least the interface and doc of NetworkSimplex).

However simple this task seemed after deciding the interface related questions, it took a few hours to correctly implement, document and test everything.

Here are the changes:

• 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.

[Peter Kovacs]

Maybe there is one question, that wasn't confirmed by anyone else before. Is it good to have INF member in NS, or should we use another name, e.g. INF_BOUND, INF_FLOW or something else (since it is only for the upper bounds, not the costs).

[Peter Kovacs]

[6c408d864fa1] went to the main branch.