COIN-OR::LEMON - Graph Library

Opened 7 years ago

Closed 6 years ago

#454 closed enhancement (done)

Insufficient checking for feasibility in min cost flow algorithms

Reported by: Peter Kovacs Owned by: Peter Kovacs
Priority: minor Milestone: LEMON 1.3 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description

Pierre Chardaire reported this issue on the lemon-devel mailing list.

Attachments (2)

454-daa8c50a0371.patch (5.0 KB) - added by Peter Kovacs 7 years ago.
454-ee9bac10f58e-debug-checking.patch (3.6 KB) - added by Peter Kovacs 7 years ago.

Download all attachments as: .zip

Change History (8)

Changed 7 years ago by Peter Kovacs

Attachment: 454-daa8c50a0371.patch added

comment:1 Changed 7 years ago by Peter Kovacs

Status: newassigned

The attached patch [daa8c50a0371] fixes this issue and extends min_cost_flow_test.cc with corresponding test cases.

comment:2 in reply to:  1 Changed 7 years ago by Peter Kovacs

There was a discussion about this issue on the lemon-devel mailing list. The conclusion is that we consider the lower>upper case as an invalid input instead of a valid but infeasible one (similarly to other network flow algorithms), mainly because the Hoffman condition does not work for that. Thus the proposed patch won't be applied.

Other suggestions:

  1. Make this requirement more visible in the doc.
  2. Introduce a validity checker function for the min cost flow algorithms, e.g. if (ns.checkValidity() && ns.run() == NetworkSimplex::OPTIMAL) {...}. Note that it is not the same as #292, since it would check the validity of the input, not the correctness of the results. This idea would also apply to other algorithms, e.g. Circulation.

comment:3 Changed 7 years ago by Alpar Juttner

Milestone: LEMON 1.3 releaseLEMON 1.4 release

comment:4 Changed 7 years ago by Peter Kovacs

The attached new patch [ee9bac10f58e] uses the LEMON_DEBUG macro in the min cost flow algorithms to check if lower <= upper holds for each arcs (just like Circulation class does). Such checkings are disabled by default as they may have performance overhead, but they can be enabled by defining LEMON_ENABLE_DEBUG. For more information, see the doc.

Changed 7 years ago by Peter Kovacs

comment:5 Changed 7 years ago by Peter Kovacs

Milestone: LEMON 1.4 releaseLEMON 1.3 release
Priority: majorminor
Type: defectenhancement

comment:6 Changed 6 years ago by Alpar Juttner

Resolution: done
Status: assignedclosed

[ee9bac10f58e] has been merged to the main branch

Note: See TracTickets for help on using tickets.