[Lemon-user] User Data Structures

[Vivek Periaraj]

Hi Alpar, 


Thanks. 


I have an additional constraint of type E x <= D 


Where E and D are integers. There is a way to satisfy this constraint without affecting the optimality conditions, by modifying the simplex method as described in this paper: 


http://www.researchgate.net/publication/223407975_Network_flow_problems_with_one_side_constraint_A_comparison_of_three_solution_methods 


I am also expecting my solution to be in integers which can be achieved by exploiting the integrality property of the network flow problems. I will look at the Lagrangian approach. Thanks for the suggestion. 


Regards, 
Vivek. 

----- Original Message -----

From: "Alpar Juttner" <alpar at cs.elte.hu> 
To: "Vivek Periaraj" <vivek.periaraj at gmail.com> 
Cc: lemon-user at lemon.cs.elte.hu 
Sent: Friday, September 13, 2013 11:12:09 AM 
Subject: Re: [Lemon-user] User Data Structures 

Hi, 

> I am new to Lemon. I would like to know if there is a way to access 
> user data structures from within an algorithm. 

You have access to anything for the source code is in your hand! 
The implementation of most of the algorithms are quite easy to 
understand and to modify once you know how the algorithm works. 

> I have a max flow problem with a side constraint which I intend to 
> solve using Network Simplex method. 

What do you actually mean by side constraint? 

For example, you may want to solve the minimum cost flow problem with 
and additional w*x <= B type constraint (i.e. if you want to keep the 
weighted some of the flow values below a limit B). 

Unfortunately, the Network simplex algorithm cannot handle this problem 
for it heavily rely on the special structure of the basic solutions of 
the network flow problem. 

Instead you should either 
* formulate the whole problem as an LP and solve it with an LP 
solver or 
* use a Lagrange relaxation technique for eliminating the 
additional constraint. 

The first choice is the easiest. The second one needs some programming, 
but may be more efficient. 

Regards, 
Alpar 



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20130915/5a0c24b6/attachment.html>