Opened 13 years ago
Last modified 11 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 )
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 13 years ago by
Description: | modified (diff) |
---|
comment:2 Changed 13 years ago by
Owner: | changed from Alpar Juttner to Peter Kovacs |
---|---|
Status: | new → assigned |
comment:3 Changed 13 years ago by
Summary: | Network Simplex alg. for a simplyfied problem → Network Simplex alg. for a simplified problem |
---|
comment:4 Changed 11 years ago by
Owner: | changed from Peter Kovacs to Alpar Juttner |
---|---|
Status: | assigned → new |
Note: See
TracTickets for help on using
tickets.