COIN-OR::LEMON - Graph Library

Opened 8 years ago

Last modified 4 months ago

#261 reopened enhancement

Support floating-point data in min-cost flow algorithms

Reported by: alpar Owned by: kpeter
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 kpeter 6 years ago.

Download all attachments as: .zip

Change History (13)

comment:1 Changed 8 years ago by kpeter

  • Status changed from new to assigned
  • Summary changed from Support real value types in NetworkSimplex, PHASE II. to 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 follow-up: Changed 8 years ago by kpeter

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

comment:3 in reply to: ↑ 2 ; follow-up: Changed 8 years ago by alpar

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 ; follow-up: Changed 8 years ago by 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". 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 ; follow-up: Changed 8 years ago by alpar

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 8 years ago by kpeter

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 8 years ago by kpeter

  • Milestone changed from LEMON 1.2 release to LEMON 1.3 release

comment:8 Changed 6 years ago by kpeter

  • Summary changed from Support real value data in NetworkSimplex to Support real value data in min cost flow algorithms

comment:9 Changed 6 years ago by kpeter

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 6 years ago by alpar

  • Resolution set to fixed
  • Status changed from assigned to closed

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

comment:11 Changed 4 years ago by kpeter

  • Milestone changed from LEMON 1.3 release to LEMON 1.4 release
  • Resolution fixed deleted
  • Status changed from closed to 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 4 months ago by kpeter

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