[Lemon-devel] Network Simplex

[Alpar Juttner]

On Thu, 2012-12-06 at 14:18 +0000, Pierre Chardaire (CMP) wrote:

> You distinction is not common in the OR community,

In fact, it _is_ very common. Consider just the following examples:

        1. Max feasible flow = Min cut theorem.
        
        It is true only if we _assume_ cap(a)>=0.
        
        2. Feasibility condition for min calculation (Hoffman theorem)
        
        From the book Ahuja, Magnanti, Orlin: "Network Flows", page 195:
        
                Theorem  6.11 (Circulation Feasibility Conditions). A
                circulation problem with nonnegative bounds on arc flow
                is feasible if and only if for every set S of nodes
                	sum(l_ij:(ij)\in(V\S,S)) <= sum(u_ij:(ij)\in(S,V\S))
                
        Again, this is true only if we _assume_ that l_ij<=u_ij.
        
        3. Dijkstra algorithm.
        It runs and terminates and returns a path for any length
        function, but it works correctly only _assuming_ that the
        lengths are non-negative.
        Should Dijkstra alg. test the nonnegativity or can it just
        assume that?
        
Notice the differentiation between "feasibility condition" and
"assumption"="precondition" above. Fulfilling of the later one
translates to "valid input" when it comes to implementation in LEMON.


> Note: I am not totally ignorant in this field,

To be honest it was clear to me, and I highly regard your opinion.
Also, please do not consider my answers as a straightaway denial. I'm
basically open to everything, but I would like to understand all the
aspects of a change like the one you proposed. (Peter can tell you
horror stories about e.g how the NetworkSimplex API and implementation
was born. Hopefully for me, he will do it in private :) )

Our main policies when designing the LEMON API are:
      * It should be as clean and uniform as possible.
      * It should be comfortable to use.
      * It should allow the fastest possible implementation.
      * Strictly maintain backward compatibility.

All in all, we want to avoid "it just seemed reasonable at that time"
type design decisions.

>  as I designed my own network simplex algorithm for non-oriented
> multi-commodity flow problems:

This looks very interesting. Multi-commodity flows are really a weak
point of LEMON right now.

All the best,
Alpar

> 
> @article{DBLP:journals/ior/ChardaireL02,
>   author    = {Pierre Chardaire and
>                Abdel Lisser},
>   title     = {Simplex and Interior Point Specialized Algorithms for Solving
>                Nonoriented Multicommodity Flow Problems},
>   journal   = {Operations Research},
>   volume    = {50},
>   number    = {2},
>   year      = {2002},
>   pages     = {260-276},
>   ee        = {http://dx.doi.org/10.1287/opre.50.2.260.436},
>   bibsource = {DBLP, http://dblp.uni-trier.de}
> }
> 
> Cheers,
> 
> Pierre.
> 
> >-----Original Message-----
> >From: Alpár Jüttner [mailto:alpar.juttner at gmail.com] On Behalf Of Alpar
> >Juttner
> >Sent: Thursday, December 06, 2012 2:03 PM
> >To: Kovács Péter
> >Cc: Pierre Chardaire (CMP); lemon-devel at lemon.cs.elte.hu
> >Subject: Re: [Lemon-devel] Network Simplex
> >
> >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.
> >
>