[Lemon-devel] Network Simplex

[Kovács Péter]

Hi All,

 > (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 :) )

No horror stories, just challenging discussions. :) However, they were 
constructive and I think they led to rather good decisions.

Anyway, I need not tell stories in private as most of the design 
discussions are public, e.g.:
http://lemon.cs.elte.hu/trac/lemon/ticket/234
http://lemon.cs.elte.hu/trac/lemon/ticket/219

Best regards,
Peter


On 2012.12.06. 17:17, Alpar Juttner wrote:
> 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.
>>>
>>
>
>
>