[Lemon-devel] Network Simplex

Pierre Chardaire (CMP) P.Chardaire at uea.ac.uk
Thu Dec 6 15:49:02 CET 2012 

Alpar,

Thank you for the message and for dealing with issues rapidly. 
Yes that is a very fine solution.

Pierre.

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

More information about the Lemon-devel mailing list