[Lemon-devel] Network Simplex

[Pierre Chardaire (CMP)]

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.  

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