COIN-OR::LEMON - Graph Library

Opened 9 years ago

Closed 7 years ago

#403 closed defect (invalid)

Possible floating point issue in cycle_canceling.h

Reported by: Alpar Juttner Owned by: Peter Kovacs
Priority: major Milestone: LEMON 1.3 release
Component: core Version: hg main
Keywords: Cc: meistermicha@…
Revision id:

Description

From the lemon-devel@… mailing list:

Hello,

I am using the lemon library 1.2.1 to solve a minCostFlow-problem. I encountered a problem by using the cyclecanceling algorithm. Sometimes, depending on graph and flow settings, the function hangs in an infinity loop at cycle_canceling.h at line 935:

while (mmc.findCycleMean() && mmc.cycleCost() < 0) {

I do not have deep insight into the algorithm but by debugging I saw that mmc.cycleCost() returns constantly values around -10e-17. Everything seems to work correctly by changing the line to

while (mmc.findCycleMean() && mmc.cycleCost() < -10e-10) {

Maybe this is a rounding issue?

Regards, Michael

Change History (3)

comment:1 Changed 9 years ago by Peter Kovacs

Type: defectenhancement

The current min cost flow implementations support only integer data. It is a known and documented limitation of these codes.

comment:2 Changed 9 years ago by Peter Kovacs

I think we should close this ticket. See e.g. #261 for the related feature request.

comment:3 Changed 7 years ago by Alpar Juttner

Resolution: invalid
Status: newclosed
Type: enhancementdefect
Note: See TracTickets for help on using tickets.