COIN-OR::LEMON - Graph Library

Opened 10 years ago

Last modified 19 months 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)

261-eb12ad2789fc-real-costs-capacity-scaling.patch (868 bytes) - added by Peter Kovacs 7 years ago.

Download all attachments as: .zip

Change History (13)

comment:1 Changed 10 years ago by Peter Kovacs

Status: newassigned
Summary: Support real value types in NetworkSimplex, PHASE II.Support real value data in NetworkSimplex

In #254 real value types are supported, but it would be nice to support floating point data as well, at least for costs.

comment:2 Changed 10 years ago by Peter Kovacs

It would be important for other MCF algorithms, and Suurballe algorithm, as well.

comment:3 in reply to:  2 ; Changed 9 years ago by Alpar Juttner

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 in reply to:  3 ; Changed 9 years ago by Peter Kovacs

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 in reply to:  4 ; Changed 9 years ago by Alpar Juttner

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 in reply to:  5 Changed 9 years ago by Peter Kovacs

Replying to alpar:

Suurballe is certainly not "unsafe". It just performs constant number of Dijkstra algorithm calls.

You're absolutely right, see #323.

comment:7 Changed 9 years ago by Peter Kovacs

Milestone: LEMON 1.2 releaseLEMON 1.3 release

comment:8 Changed 7 years ago by Peter Kovacs

Summary: Support real value data in NetworkSimplexSupport real value data in min cost flow algorithms

Changed 7 years ago by Peter Kovacs

comment:9 Changed 7 years ago by Peter Kovacs

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 7 years ago by Alpar Juttner

Resolution: fixed
Status: assignedclosed

[eb12ad2789fc] has been pushed to the main branch. Thanks.

comment:11 Changed 5 years ago by Peter Kovacs

Milestone: LEMON 1.3 releaseLEMON 1.4 release
Resolution: fixed
Status: closedreopened

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 19 months ago by Peter Kovacs

Summary: Support real value data in min cost flow algorithmsSupport floating-point data in min-cost flow algorithms
Note: See TracTickets for help on using tickets.