[Lemon-user] Optimal Solution for MCF Problem

[Kovács Péter]

Hi All,

As Alpár wrote, the network simplex algorithm finds an optimal solution 
to any MCF problem, but only if such a solution exists. The run() method 
returns the status of the problem: OPTIMAL, INFEASIBLE, or UNBOUNDED. 
See the API doc here:
http://lemon.cs.elte.hu/pub/doc/1.3.1/a00276.html#a591276ea8f1afbe9d24bd1c1d48b0f53

Note that there are no trivial conditions that ensure the existence of 
feasible or optimal solutions. A flow algorithm is required to determine 
them.

Regards,
Péter



> Hi,
>
> I'm not sure what do you mean by Question 1, but as far as Question 2
> is concerned, the answer is yes, the network simplex algorithm finds an
> optimal solution to (a quite general version of) MCF problems.
>
> Regards,
> Alpár
>
>
> On Tue, 2016-06-21 at 08:23 +0000, T.A. Heba Essam wrote:
>> Dear all,
>>
>> 1- If satisfying the feasibility conditions (integers, non-negative
>> costs, directed graph..etc) gives us a feasible solution for a MCF
>> problem. What does provide an optimal solution? what are the
>> conditions?
>>
>> 2- Also, does the network simplex algorithm implemented by LEMON
>> finds an "optimal" solution for a given MCF problem?
>>
>> Thanks,
>> Heba Essam
>>
>>
>> _______________________________________________
>> Lemon-user mailing list
>> Lemon-user at lemon.cs.elte.hu
>> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
>