Insufficient checking for feasibility in min cost flow algorithms

[Peter Kovacs]

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

[Peter Kovacs]

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

[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.

[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.

[Alpar Juttner]

[ee9bac10f58e] has been merged to the main branch