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