[Lemon-devel] Network Simplex

[Kovács Péter]

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