[Lemon-devel] Network Simplex

[Pierre Chardaire (CMP)]

Péter, Alpar,

As mentioned early this specific distinction between validity and infeasibility is unconventional in this case. 
So, if the patch does not imply considerable overhead I would be in favour of it.

Pierre.

>-----Original Message-----
>From: Kovács Péter [mailto:kpeter at inf.elte.hu]
>Sent: Thursday, December 06, 2012 12:29 PM
>To: Alpar Juttner
>Cc: Pierre Chardaire (CMP); lemon-devel at lemon.cs.elte.hu
>Subject: Re: [Lemon-devel] Network Simplex
>
>Hi All,
>
>I generally agree with Alpar, but the distinction between invalid and infeasible
>is not so clear for me in this particular case. It seems to be similar to the case
>when the sum of node supply values is positive, which is considered as
>infeasible, though it can also be considered as invalid for similar reasons. (This
>prerequisite is explicitly emphasized in the doc.)
>
>The additional checkings in the patch #454 do not imply considerable
>overhead to the algorithms. Thus I don't find the patch problematic, but I also
>don't mind if it is not applied.
>
>Peter
>
>
>
>On 2012.12.06. 11:51, Alpar Juttner wrote:
>> 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
>>>
>>
>>
>>