COIN-OR::LEMON - Graph Library

Opened 10 years ago

Last modified 8 years ago

#222 new enhancement

Network Simplex alg. for a simplified problem

Reported by: Alpar Juttner Owned by: Alpar Juttner
Priority: major Milestone:
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description (last modified by Peter Kovacs)

A simpler (but in fact equivalent) form of the Network Flow Problems when we have no upper limit on the arcs. We can also assume that the lower limit is 0 everywhere.

In this case Network Simplex algorithms becomes much easier:

  • A basis is just a tree, and it's trivial to obtaine both the primal and the dual solutions from it.
  • A starting dual feasible solution is just a feasible potential w.r.t. the cost, so it can be computed by a shortest path algorithm.

Change History (4)

comment:1 Changed 10 years ago by Peter Kovacs

Description: modified (diff)

comment:2 Changed 10 years ago by Peter Kovacs

Owner: changed from Alpar Juttner to Peter Kovacs
Status: newassigned

comment:3 Changed 10 years ago by Alpar Juttner

Summary: Network Simplex alg. for a simplyfied problemNetwork Simplex alg. for a simplified problem

comment:4 Changed 8 years ago by Peter Kovacs

Owner: changed from Peter Kovacs to Alpar Juttner
Status: assignednew
Note: See TracTickets for help on using tickets.