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.