[Lemon-devel] Network Simplex

[Alpar Juttner]

Hi Pierre and Peter,

> Yes, such feasibility checking is indeed missing from the min cost flow 
> classes, including NetworkSimplex. Thank you for reporting this bug.

I don't thing it is a bug. One must notice the subtle but important
difference between an (in)valid and an (in)feasible input.

      * Most algorithms have some prerequisite on the input it can
        process. An input is VALID if it meets these requirements.
        IUsing LEMON - as a general policy - it is the responsibility of
        the user to provide valid input, the algorithms do _not_ check
        the validity(*). The behavior of the algorithm on an infeasible
        input is undefined, including even crashes, memory corruption
        etc. On the other hand, an algorithm should run correctly on
        _any_ valid input.
      * A valid input can still be FEASIBLE (== solvable) or INFEASIBLE
        (== unsolvable). We expect that the algorithm runs correctly in
        both cases, and even more, we expect some proof of correctness
        of the result. In case of a feasible input we need the (optimal)
        solution, of course. In case of an infeasible input we want
        something more than just a 'NO' answer, we need some kind of a
        proof of the infeasibility. (**)

As far as the network simplex algorithm is concerned, it is assumed that
l(a)<=u(a) holds for each arc, the input is INVALID if it doesn't. This
prerequisite is explicitly stated in the doc of the network flow
formulation ( http://lemon.cs.elte.hu/pub/doc/1.2.3/a00005.html ),
though I admit it is a bit hidden.

And this assumption is not by accident, but because it makes the proof
of infeasibility cleaner and more compact. (The Hoffman condition for
the feasibility of a flow/circulation problem holds only with the
l(a)<=u(a) assumption.)

Regards,
Alpar

(*) The rational behind is runtime efficiency - do not spend time on
checking something that we know it is true.
(**) For a feasible input, a proof of optimality is also provided.

>  I 
> made a patch for fixing it, see:
> http://lemon.cs.elte.hu/trac/lemon/ticket/454
> 
> Best regards,
> Peter
> 
> 
> On 2012.12.05. 16:45, Pierre Chardaire (CMP) wrote:
> > I found a small problem with the Network Simplex.
> >
> > I was iteratively changing the graph and rerunning, and made a mistake:
> >
> > I set an arc upper limit capacity to 0 and forgot to unset a lower limit
> > capacity (that was 3 in the first place)
> >
> > After running I got a result with the status OPTIMAL. The arc concerned
> > had a flow of 3 units.
> >
> > Pierre.
> >
> > School of Computing Sciences
> >
> > University of East Anglia
> >
> > Norwich, NR4 7TJ, UK
> >
> >
> >
> > _______________________________________________
> > Lemon-devel mailing list
> > Lemon-devel at lemon.cs.elte.hu
> > http://lemon.cs.elte.hu/mailman/listinfo/lemon-devel
> >
> 
> _______________________________________________
> Lemon-devel mailing list
> Lemon-devel at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-devel
>