Opened 16 years ago
Last modified 8 years ago
#261 reopened enhancement
Support floating-point data in min-cost flow algorithms
| Reported by: | Alpar Juttner | Owned by: | Peter Kovacs |
|---|---|---|---|
| Priority: | major | Milestone: | LEMON 1.4 release |
| Component: | core | Version: | hg main |
| Keywords: | Cc: | ||
| Revision id: |
Description
This is a follow-up of #254.
Attachments (1)
Change History (13)
comment:1 Changed 16 years ago by
| Status: | new → assigned |
|---|---|
| Summary: | Support real value types in NetworkSimplex, PHASE II. → Support real value data in NetworkSimplex |
comment:2 follow-up: 3 Changed 16 years ago by
It would be important for other MCF algorithms, and Suurballe algorithm, as well.
comment:3 follow-up: 4 Changed 15 years ago by
Replying to kpeter:
It would be important for other MCF algorithms, and Suurballe algorithm, as well.
Suurballe used to support it in the 0.x series, didn't it?
comment:4 follow-up: 5 Changed 15 years ago by
Replying to alpar:
Suurballe used to support it in the 0.x series, didn't it?
I think most of the MCF algorithms and Suurballe correctly handle floating point costs without any modification, except for the usage of the tolerance concept, so they could be somewhat "unsafe". This question should be carefully investigated for all algorithms. I would like to return to this task after I have ported all MCF algorithms, see #180.
comment:5 follow-up: 6 Changed 15 years ago by
Replying to kpeter:
Replying to alpar:
Suurballe used to support it in the 0.x series, didn't it?
I think most of the MCF algorithms and Suurballe correctly handle floating point costs without any modification, except for the usage of the tolerance concept, so they could be somewhat "unsafe".
Suurballe is certainly not "unsafe". It just performs constant number of Dijkstra algorithm calls.
comment:6 Changed 15 years ago by
comment:7 Changed 15 years ago by
| Milestone: | LEMON 1.2 release → LEMON 1.3 release |
|---|
comment:8 Changed 13 years ago by
| Summary: | Support real value data in NetworkSimplex → Support real value data in min cost flow algorithms |
|---|
Changed 13 years ago by
| Attachment: | 261-eb12ad2789fc-real-costs-capacity-scaling.patch added |
|---|
comment:9 Changed 13 years ago by
Similarily to Suurballe, CapacityScaling also handles non-integer costs correctly without any modification. The attached patch [eb12ad2789fc] fixes the doc by removing this unnecessary requirement.
comment:10 Changed 13 years ago by
| Resolution: | → fixed |
|---|---|
| Status: | assigned → closed |
[eb12ad2789fc] has been pushed to the main branch. Thanks.
comment:11 Changed 11 years ago by
| Milestone: | LEMON 1.3 release → LEMON 1.4 release |
|---|---|
| Resolution: | fixed |
| Status: | closed → reopened |
Should we consider increased support for non-integer data?
It would be nice if NetworkSimplex accepted non-integer costs as well as non-integer capacity, supply, and flow values.
comment:12 Changed 8 years ago by
| Summary: | Support real value data in min cost flow algorithms → Support floating-point data in min-cost flow algorithms |
|---|
In #254 real value types are supported, but it would be nice to support floating point data as well, at least for costs.