COIN-OR::LEMON - Graph Library

Opened 10 years ago

Closed 10 years ago

#234 closed task (fixed)

Port and revise Network Simplex algorithm

Reported by: Peter Kovacs Owned by: Peter Kovacs
Priority: major Milestone: LEMON 1.1 release
Component: core Version:
Keywords: Cc:
Revision id:

Description

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

Attachments (10)

ns-port-697d61bb33f4.patch (55.0 KB) - added by Peter Kovacs 10 years ago.
Port NS from SVN -r3520
ns-port-7f07ddefb52d.patch (55.0 KB) - added by Peter Kovacs 10 years ago.
The same as [697d61bb33f4] with better commit log
dimacs-solver-726568ea7ed4.patch (1.9 KB) - added by Peter Kovacs 10 years ago.
Add MCF support for dimacs-solver
mcf-port.bundle (11.2 KB) - added by Peter Kovacs 10 years ago.
ns-e8349c6f12ca--0e7416abfce8.bundle (18.0 KB) - added by Peter Kovacs 10 years ago.
ns-e8349c6f12ca--c7d160f73d52.bundle (18.7 KB) - added by Peter Kovacs 10 years ago.
ns-types-9ad8d2122b50.patch (16.5 KB) - added by Peter Kovacs 10 years ago.
ns-all-together-e8349c6f12ca--6ac5d9ae1d3d.bundle (20.5 KB) - added by Peter Kovacs 10 years ago.
10 changesets about NetworkSimplex
ns-b1811c363299-19b6f20e0ea2-e3d9bff447ed.bundle (1.8 KB) - added by Peter Kovacs 10 years ago.
ns-mapcopy-111698359429.patch (24.0 KB) - added by Peter Kovacs 10 years ago.

Download all attachments as: .zip

Change History (30)

Changed 10 years ago by Peter Kovacs

Attachment: ns-port-697d61bb33f4.patch added

Port NS from SVN -r3520

comment:1 Changed 10 years ago by 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.

Changed 10 years ago by Peter Kovacs

Attachment: ns-port-7f07ddefb52d.patch added

The same as [697d61bb33f4] with better commit log

Changed 10 years ago by Peter Kovacs

Add MCF support for dimacs-solver

comment:2 Changed 10 years ago by Peter Kovacs

Status: newassigned

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.

comment:3 Changed 10 years ago by 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).
  1. 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.
  1. 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(), "...");
    

comment:4 in reply to:  2 ; Changed 10 years ago by 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].

comment:5 in reply to:  3 Changed 10 years ago by 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.

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

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

Changed 10 years ago by Peter Kovacs

Attachment: mcf-port.bundle added

comment:6 in reply to:  4 Changed 10 years ago by 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].

Changed 10 years ago by Peter Kovacs

comment:7 Changed 10 years ago by 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.

Changed 10 years ago by Peter Kovacs

comment:8 Changed 10 years ago by 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.

comment:9 Changed 10 years ago by Peter Kovacs

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

comment:10 Changed 10 years ago by 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.)

comment:11 Changed 10 years ago by Peter Kovacs

See #219 for an additional changeset for NetworkSimplex.

comment:12 Changed 10 years ago by 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.

Changed 10 years ago by Peter Kovacs

Attachment: ns-types-9ad8d2122b50.patch added

comment:13 Changed 10 years ago by 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.

comment:14 Changed 10 years ago by 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.

Changed 10 years ago by Peter Kovacs

10 changesets about NetworkSimplex

comment:15 Changed 10 years ago by Alpar Juttner

Resolution: fixed
Status: assignedclosed

All the relevant changesets are in the main branch now.

comment:16 Changed 10 years ago by Peter Kovacs

Resolution: fixed
Status: closedreopened

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

  1. 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)?

Changed 10 years ago by Peter Kovacs

comment:17 Changed 10 years ago by 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.

comment:18 Changed 10 years ago by Alpar Juttner

Resolution: fixed
Status: reopenedclosed

comment:19 Changed 10 years ago by Peter Kovacs

Resolution: fixed
Status: closedreopened

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

Changed 10 years ago by Peter Kovacs

comment:20 Changed 10 years ago by Peter Kovacs

Resolution: fixed
Status: reopenedclosed

[111698359429] went to the main branch.

Note: See TracTickets for help on using tickets.