[Lemon-devel] Network Simplex

[Kovács Péter]

Hi All,

I generally agree with Alpar, but I also agree with Pierre that the 
distinction between invalid and infeasible is not so clear in this case.

The min cost flow problem formulation explicitly says that:
  (a) l(a)<=u(a) must hold for each arc;
  (b) sum of node supply values must be zero or negative.
Currently, violaion of (a) means the input is invalid, while violation 
of (b) only implies that the problem is infeasible. Although this 
distinction may be reasonable, it could be misleading for a user (or a 
developer like me :)).

In fact, the additional checkings for (a) 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
>>
>
>
>