[Lemon-devel] Network Simplex

[Pierre Chardaire (CMP)]

Alpar,

Thank you for the reply. I meant as far as the network simplex algorithm is concerned. I told my colleague next door (he is also an OR person) and he also found it strange that the algorithm did not return infeasible when l(a)>u(a). Obviously, other types of algorithm like Dijkstra's or even other flow algorithms are not quite of the same nature. 

But maybe my views are slanted towards linear programming.  The solution you proposed in a previous e-mail is perfectly fine, and the idea of having methods that a user can employ to perform a precondition check on the algorithms is an excellent one. I also perfectly understand all the points you make regarding the design of a good library. If you are interested in multi-commodity flows I could see what I can do, but I'll have to learn more about lemon first. 

Best regards,

Pierre.

>-----Original Message-----
>From: Alpár Jüttner [mailto:alpar.juttner at gmail.com] On Behalf Of Alpar
>Juttner
>Sent: Thursday, December 06, 2012 4:17 PM
>To: Pierre Chardaire (CMP)
>Cc: Kovács Péter; lemon-devel at lemon.cs.elte.hu
>Subject: Re: [Lemon-devel] Network Simplex
>
>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.
>> >
>>
>