Port and revise Network Simplex algorithm

[Peter Kovacs]

Network Simplex is the fastest MCF implementation in LEMON. It should be ported first and the interface should be clarified. Then the remaining MCF algorithms should be ported with exactly the same interface (see #180).

[Peter Kovacs]

Port NS from SVN -r3520

[Peter Kovacs]

[697d61bb33f4] contains a port of network_simplex.h algorithm and the min_cost_flow_test.cc. The test file was revised and improved. Not it checks only the NetworkSimplex class.

[Peter Kovacs]

The same as [697d61bb33f4] with better commit log

[Peter Kovacs]

Add MCF support for dimacs-solver

[Peter Kovacs]

In [697d61bb33f4] the commit log does not contain reference for this ticket, so I attached [7f07ddefb52d], which is the same, but with better commit log.

[726568ea7ed4] adds MCF support for dimacs-solver.

[Peter Kovacs]

Some questions turned up about the MCF class interface.

1. Maybe it would be better to have only two template parameters for the classes: the graph type and the value type, and a few template run() functions with different parameter lists. It would have several advantages. E.g. the lower bound map type needn't be specified in those cases when it is not used (now it is necessary whether lower bounds are used or not).

2. It seems to be a good idea to have a template totalCost() function, since it could be an order of magnitude larger than all individual data values. So the total cost could be computed using a larger data type than the value type of the maps.

3. NS must be used with integral data types. It is noted in the doc, however it isn't checked at all. So it could be compiled and run using e.g. double type, but it gives bad results. It would better to check this condition somehow. E.g. with

   LEMON_DEBUG(std::numeric_limits<Value>::is_integer(), "...");
   

[Alpar Juttner]

Replying to kpeter:

In [697d61bb33f4] the commit log does not contain reference for this ticket, so I attached [7f07ddefb52d], which is the same, but with better commit log.

make distcheck fails on [7f07ddefb52d].

[Alpar Juttner]

Replying to kpeter:

Some questions turned up about the MCF class interface.

1. Maybe it would be better to have only two template parameters for the classes: the graph type and the value type,

I'm certainly in favor of this.

and a few template run() functions with different parameter lists. It would have several advantages.

I would prefer to see separate template functions for setting the bounds and the supply function and a simple run(). The setting functions should also set a flag, so that run() can apply some default setting if something was not given.

For the sake of convenience, we may also have some parametrized version of run(), of course.

E.g. the lower bound map type needn't be specified in those cases when it is not used (now it is necessary whether lower bounds are used or not).

Hopefully we don't have to specify it even if it is used.

2. It seems to be a good idea to have a template totalCost() function, since it could be an order of magnitude larger than all individual data values. So the total cost could be computed using a larger data type than the value type of the maps.

I don't think it is important, but at least it doesn't hurt.

3. NS must be used with integral data types. It is noted in the doc, however it isn't checked at all. So it could be compiled and run using e.g. double type, but it gives bad results.

What is the reason for that? Isn't it possible to have it working reliably with doubles?

It would better to check this condition somehow. E.g. with

LEMON_DEBUG(std::numeric_limits<Value>::is_integer(), "...");

You can also use LEMON_ASSERT, as it wont affect the running time.

[Peter Kovacs]

Replying to alpar:

make distcheck fails on [7f07ddefb52d].

Yep. I forgot to modify one of the Makefile.am files.

The attached bundle contains a fixed version of the former changesets rebased on the top of the main repository: [e8349c6f12ca] and [a79ef774fae1].

[Peter Kovacs]

The attached bundle file contains five changesets. The first two ([e8349c6f12ca] and [a79ef774fae1]) are the same as in the previous bundle file.

The other three are the followings.

• [425cc8328c0e] Internal restructuring and renamings.
• [8c3112a66878] Use XTI implementation instead of ATI. It is a much faster method for storing and updating the spanning tree structure. For more information see the commit log.
• [0e7416abfce8] Rework the interface according to the above ideas.

Here are some examples for using the new interface. For more information see the documentation.

  ns.capacityMap(cap).costMap(cost)
    .supplyMap(sup).run();
  ns.run(cap, cost, sup);

  ns.lowerMap(lower).upperMap(upper).costMap(cost)
    .supplyMap(sup).run();
  ns.run(lower, upper, cost, sup);

  ns.capacityMap(cap).costMap(cost)
    .stFlow(s,t,k).run();
  ns.run(cap, cost, s, t, k);

  ns.lowerMap(lower).upperMap(upper).costMap(cost)
    .stFlow(s,t,k).run();
  ns.run(lower, upper, cost, s, t, k);

If you use the run() function, then the parameters can be set with separate functions. If any of these functions is not called, then default values are used. They are 0 for the lower bounds, std::numeric_limits<Value>::max() for the upper bounds, 1 for the costs and 0 for the supply values.

[Peter Kovacs]

After some personal discussion we agreed that the overloaded run() functions should be removed, since it could be annoying that the same parameters appear on different positions. Thus only the named parameters and the simple run() function will be supported.

I attached a bundle file​, that conatains the first 4 changesets of the previous one, and two more changesets:

• [5232721b3f14] is the fixed variant of the interface reworking. It contains a new function boundMaps(), stFlow() is renamed to stSupply() and the overloaded run() functions are removed.
• [c7d160f73d52] supports multiple run() calls in NetworkSimplex. By default all the parameters given by the different functions are kept for the next run() call, however there is a reset() function to reset them. See the documentation for examples.

[Peter Kovacs]

Could you please tell me your opinion about this new interface (the named paramaters, the multiple run() ability and the reset() function)?

[Peter Kovacs]

Another question: should the reset() function also reset the effect of the external map setter functions flowMap() and potentialMap()? Now it does not reset them. (The values of these maps are not used for the next run, they are just overwritten.)

[Peter Kovacs]

See #219 for an additional changeset for NetworkSimplex.

[Peter Kovacs]

My last question: which would be the best function name for getting the total (minimum) flow cost: totalCost(), flowCost() or minCost()? Now the first one is used.

[Peter Kovacs]

[9ad8d2122b50] is another patch for NS, which separates the value types used for flow and cost values.

I think the last bundle file along with this changeset could be merged into the main branch.

As soon as they are merged, the DIMACS solver for MCF (that is in the bundle file) should be updated according to the changes made about infinite capacities, see #243.

[Peter Kovacs]

[e6927fe719e6] is a new changeset for NS, that supports >= and <= inequalities in the supply/demand constraints, see #219. It is on the top of [6ac5d9ae1d3d] (see #254), which is on the top of [9ad8d2122b50] (attached to this ticket).

In order to simplify our work, I attached a bundle file that contains all the 10 changesets about NetworkSimplex that are candidates to be pushed into the main branch.

[Peter Kovacs]

10 changesets about NetworkSimplex

[Alpar Juttner]

All the relevant changesets are in the main branch now.

[Peter Kovacs]

Other questions have arisen.

1. ProblemType and problemType() in NetworkSimplex are about a really different thing than ProblemType, primalType() and dualType() in LP solvers. The former one is about changing between LEQ and GEQ, while in LP it is used for INFEASIBLE, FEASIBLE, OPTIMAL, UNBOUNDED etc. So probably we should find a better name in NetworkSimplex. The following names have been suggested.
   • supplyType()
   • constraintType()
   • problemForm()
   • or something with direction?

(Maybe the most precise would be supplyConstraintType() or supplyConstraintDirection(), but they are too long.)

2. If we would like to allow infinite capacities and negative costs (or negative infinite lower bounds with positive costs), than an MCF problem can be unbounded, so the current bool valued run() function is not enough. Should we give back these status results by the run() function itself or run() should be kept two-state and we should introduce a getter function for the type/state (e.g. INFEASIBLE, OPTIMAL, UNBOUNDED)?

[Peter Kovacs]

The attached bundle file contains three changesets:

• [b1811c363299] A bug fix.
• [19b6f20e0ea2] Support GEQ and LEQ supply constraints in dimacs-solver (along with the usage of infty parameter, which was introduced to the dimacs readers after MCF support was made for dimacs-solver). See also #219.
• [e3d9bff447ed] Exploit the changes of #190 in the test file.

[Peter Kovacs]

[111698359429] contains the following modifications in order to have less map copying in NS.

• The graph is copied in the constructor instead of the init() function. It must not be modified after the class is constructed.
• The maps are copied once (instead of twice).
• Remove FlowMap, PotentialMap typedefs and flowMap(), pontentialMap() setter functions.
• flowMap() and potentialMap() query functions copy the values into the given map (reference) instead of returning a const reference to a previously constructed map.

[Peter Kovacs]

[111698359429] went to the main branch.