[Lemon-devel] Network Simplex

[Alpar Juttner]

On Thu, 2012-12-06 at 13:28 +0100, Kovács Péter wrote:
> Hi All,
> 
> I generally agree with Alpar, but the distinction between invalid and 
> infeasible is not so clear for me in this particular case.

I would say, an input is valid if the Hoffman condition works for that.

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

This is a wrong analogy.
Of course, we can always require more validity condition, is just
reduces the generality of the algorithm but doesn't affects its
correctness.
Removing the u<=l prerequisite would be the other way around.

Alpar

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