COIN-OR::LEMON - Graph Library

Opened 10 years ago

Closed 10 years ago

#270 closed enhancement (fixed)

Support infinite and negative data in NetworkSimplex

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

Description

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

Attachments (3)

circ-inf-547e6b876ee1.patch (2.7 KB) - added by Peter Kovacs 10 years ago.
270-266-28f58740b6f8.patch (4.4 KB) - added by Peter Kovacs 10 years ago.
ns-negative-6c408d864fa1.patch (43.8 KB) - added by Peter Kovacs 10 years ago.

Download all attachments as: .zip

Change History (14)

Changed 10 years ago by Peter Kovacs

Attachment: circ-inf-547e6b876ee1.patch added

comment:1 Changed 10 years ago by Peter Kovacs

Status: newassigned

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

comment:2 Changed 10 years ago by Peter Kovacs

Summary: Support infinte and negative data in NetworkSimplexSupport infinite and negative data in NetworkSimplex

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

comment:4 Changed 10 years ago by Peter Kovacs

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

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

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

Changed 10 years ago by Peter Kovacs

Attachment: 270-266-28f58740b6f8.patch added

comment:7 Changed 10 years ago by Alpar Juttner

Resolution: done
Status: assignedclosed

comment:8 Changed 10 years ago by Peter Kovacs

Resolution: done
Status: closedreopened

There is outstanding issue of reworking the NetworkSimplex interface.

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

Changed 10 years ago by Peter Kovacs

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

comment:11 Changed 10 years ago by Peter Kovacs

Resolution: fixed
Status: reopenedclosed

[6c408d864fa1] went to the main branch.

Note: See TracTickets for help on using tickets.