COIN-OR::LEMON - Graph Library

Opened 9 years ago

Last modified 7 years ago

#222 new enhancement

Network Simplex alg. for a simplified problem

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

Description (last modified by kpeter)

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 9 years ago by kpeter

  • Description modified (diff)

comment:2 Changed 9 years ago by kpeter

  • Owner changed from alpar to kpeter
  • Status changed from new to assigned

comment:3 Changed 9 years ago by alpar

  • Summary changed from Network Simplex alg. for a simplyfied problem to Network Simplex alg. for a simplified problem

comment:4 Changed 7 years ago by kpeter

  • Owner changed from kpeter to alpar
  • Status changed from assigned to new
Note: See TracTickets for help on using tickets.