Hi. I was trying to understand how to change the code to handle mixed inequalities (e.g., = and >= together). I had it working in some cases that I tried, but I now have a small example where it is not working. I am not sure if my changes are incorrect or if there is actually a bug.<br>
<br>The only change I made was in init( ) where I loop over the nodes and set the artificial links based on whether I have GEQ vs EQ. That is, I create the augmented (internal) graph differently depending on if the constraint is GEQ or EQ. <br>
<br>I am attaching a pdf which shows the example I am trying to solve. It also shows the correct optimal solution of 257. In this particular case, all nodes (labeled 1-8 should be equality constraints), while node 9 should be a GEQ constraint.<br>
<br>I am also attaching my version of network_simplex.h. I am using the 1.2 download of LEMON. The main change is in the section starting at Line 1107. Note - I did not create any kind of API for entering the sense of the rows. Rather, just to try out the idea, I hard-code the row sense directly (see Line 1100 - note, the node labeled 9 winds up having an internal index of 0, which is why 'G' is in the 0th index).<br>
<br>I am also attaching my version of min_cost_flow_test.cc which has my example hard-coded which I used to test (using make check). I am also copying the example network here (see below).<br><br>For this small network, <br>
If all nodes have rows with >=, the optimal solution should be 140.<br>
If all the nodes have rows with = (except node 9), the optimal solution
should be 257.<br>
<br>With my changes, the code finds a solution of 256 and then stops (block-search pivot finds min=0). But, this leaves a positive flow on one of the artificial arcs so it declares the problem infeasible.<br><br>Can you please take a look at my changes for mixing inequalities? and let me know if I am missing something or have done it wrong. Any help is greatly appreciated!<br>
<br>Thanks,<br>Matt<br><br><br><br><br>char test_lgf_mg[] =<br> "@nodes\n"<br> "label sup\n"<br> " 1 10\n"<br> " 2 20\n"<br> " 3 0\n"<br> " 4 -5\n"<br>
" 5 0\n"<br> " 6 0\n"<br> " 7 -15\n"<br> " 8 -9\n"<br> " 9 -10\n"<br> "\n"<br> "@arcs\n"<br> " lo up cost\n"<br>
" 1 4 0 15 2\n"<br> " 2 9 0 10 1\n"<br> " 2 3 0 10 0\n"<br> " 2 6 0 10 6\n"<br> " 3 4 0 5 1\n"<br> " 3 5 0 10 4\n"<br> " 4 7 0 10 5\n"<br>
" 5 6 0 20 2\n"<br> " 5 7 0 15 7\n"<br> " 6 8 0 10 8\n"<br> " 7 8 0 15 9\n"<br> "\n"<br><br><br><br><br><br><br><div class="gmail_quote">On Thu, Jul 1, 2010 at 6:38 AM, Matthew Galati <span dir="ltr"><<a href="mailto:magh@lehigh.edu">magh@lehigh.edu</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><br><div class="gmail_quote"><div class="im"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
The first and maybe the fastest option is to contribute such an<br>
extension by yourself. We are more than happy to accept such a patch,<br>
and will help in all possible way to prepare it, of course.<br>
<br>
If you can't do that, you/we can still persuade Peter (the main<br>
developer of the NS code) to implement this feature. I guess this is<br>
also a pretty viable option...<br>
<br>
Anyway, I created a ticket about this enhancement in the issue tracker,<br>
see <a href="http://lemon.cs.elte.hu/trac/lemon/ticket/375" target="_blank">http://lemon.cs.elte.hu/trac/lemon/ticket/375</a><br></blockquote></div><div><br><br>This would be great! <br><br>I was - at first - thinking about the original request, where one can have a mix of EQ, GEQ, LEQ. It seems the code already handles this internally but is missing the API to accept it. Although I am not all that familiar with the data structures used - so I am not sure if it is that simple.<br>
<br>The feature to accept lower and upper bounds for rows (flow balance) would be great also - but it sounds like is more complicated to implement.<br><br>I am not sure if would be able to contribute myself - as I am not that confident in understanding the internal data structures used. But, I suppose I can try - if no one else plans to do it.<br>
<br>Thanks!<br>Matt<br><br><br> </div><br></div><br>
</blockquote></div><br>