[Lemon-devel] Network Simplex

Thu Dec 6 15:40:53 CET 2012

On Thu, 2012-12-06 at 12:03 +0000, Pierre Chardaire (CMP) wrote:
> Hi,
> 
> I agree that this is not a bug by the prerequisites mentioned in the
> documentation (I was cautious and said "little problem" in my message).
> However, I find it strange that you say "As far as the network simplex
> algorithm is concerned, it is assumed that l(a)<=u(a)".  Typically, if
> I were to try to solve a linear program with constraints of the form  
>  x <= U and x >= L (x variable, L, U, constants) and with L > U, with
> say CPLEX (even the network version if I remember correctly), the
> answer would be NO FEASIBLE SOLUTION, not INVALID INPUT. As the network
> simplex algorithm is just a specialisation of the simplex algorithm to
> a network structure the difference between validity and infeasibility
> you make is unconventional.

This is a question whether Network Simplex is "network" or "simplex".
Our approach was that it more of a "network", for it solves the "network
flow problem", and has the same interface that the other. For example,
when there is no feasible flow, we will not get an LP-type dual (which
would be a real number for each node), but instead we get a subset X of
nodes violating the Hoffman condition, which is much more useful in most
cases. However, such an X cannot be given when the problem is
"infeasible" because there is an arc for which l(a)>u(a).

> To be more constructive, it would be a good idea to have the option of
> a full feasibility check, which would mean checking trivial
> infeasibility of the form l(a) > u(a). As it would be optional this
> would affect computing time only when the option is set.

I do not like the idea of reclassifying the l(a)>u(b) from invalid to
infeasible. In addition to the reasons explained above it would also
affect the API of basically all network flow algorithms.

Instead, I suggest adding a separate checkValidity() member function to
NetworkSimplex (and to the other network flow algs). This solution would
be a bit less comfortable to use compared to your suggestion (you should
write something like
if(ns.checkValidity && ns.run() == NetworkSimplex::OPTIMAL) {...}
) but more "correct" to my eyes.

What do you think?

In addition, we should make this issue more visible in the doc.

Regards,
Alpar

On Thu, 2012-12-06 at 12:17 +0000, Pierre Chardaire (CMP) wrote:

> 
> Pierre
> 
> >-----Original Message-----
> >From: Alpár Jüttner [mailto:alpar.juttner at gmail.com] On Behalf Of Alpar
> >Juttner
> >Sent: Thursday, December 06, 2012 10:51 AM
> >To: Kovács Péter
> >Cc: Pierre Chardaire (CMP); lemon-devel at lemon.cs.elte.hu
> >Subject: Re: [Lemon-devel] Network Simplex
> >
> >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
> >>
> >
> 