[Lemon-devel] Network Simplex

[Pierre Chardaire (CMP)]

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.

Pierre

>-----Original Message-----
>From: lemon-devel-bounces at lemon.cs.elte.hu [mailto:lemon-devel-
>bounces at lemon.cs.elte.hu] On Behalf Of Pierre Chardaire (CMP)
>Sent: Thursday, December 06, 2012 12:04 PM
>To: Alpar Juttner; Kovács Péter
>Cc: lemon-devel at lemon.cs.elte.hu
>Subject: Re: [Lemon-devel] Network Simplex
>
>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
>>>
>>
>
>_______________________________________________
>Lemon-devel mailing list
>Lemon-devel at lemon.cs.elte.hu
>http://lemon.cs.elte.hu/mailman/listinfo/lemon-devel