Infeasible flow

[matbesancon]

trafficstars

When trying to solve a mincost flow on an infeasible network, we get a warning and a NaN matrix:

LightGraphsFlows.mincost_flow(g, cap, demand, cost)
glp_intopt: optimal basis to initial LP relaxation not provided
WARNING: Not solved to optimality, status: Infeasible
WARNING: Infeasibility ray (Farkas proof) not available
WARNING: Variable value not defined for component of x. Check that the model was properly solved.
3×3 Array{Float64,2}:
 NaN  NaN  NaN
 NaN  NaN  NaN
 NaN  NaN  NaN

I find it explicit enough, but we could add a optimal boolean in the response tuple, so that users can check if it was feasible and then handle the flow.
Another option would be to return the JuMP status.

[sbromberger]

Easy enough to programatically check via

a = fill(NaN, 3, 3)
all(isnan.(a))

[matbesancon]

before closing the issue, a similar problem occurs with unbounded mincost problem, in case of a path with negative cost and infinite capacity:

julia> flow = mincost_flow(g, capacity, demand, w, 5, 6)
WARNING: Not solved to optimality, status: Unbounded
6×6 Array{Float64,2}:
 0.0  0.0  0.0  1.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  1.0
 1.0  0.0  0.0  0.0  0.0  0.0
 0.0  0.0  0.0  0.0  0.0  0.0

(the path 5->1->4->6 should have a flow of +Inf)

[elchiconuevo]

Is the algorithm employed in the function mincostflow polynomial? If not, is there a possibility to replace the current function with a faster polynomial algorithm?

[matbesancon]

@elchiconuevo sorry I am replying extremely late: yes mincostflow is using a simplex solver under the hood, so polynomial in practice