[Lemon-user] equality form of min-cost network flow

[Matthew Galati]

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.

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.

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.

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).

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).

For this small network,
   If all nodes have rows with >=, the optimal solution should be 140.
   If all the nodes have rows with = (except node 9), the optimal solution
should be 257.

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.

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!

Thanks,
Matt




char test_lgf_mg[] =
  "@nodes\n"
  "label   sup\n"
  "    1    10\n"
  "    2    20\n"
  "    3     0\n"
  "    4    -5\n"
  "    5     0\n"
  "    6     0\n"
  "    7   -15\n"
  "    8    -9\n"
  "    9   -10\n"
  "\n"
  "@arcs\n"
  "     lo up cost\n"
  " 1 4 0  15 2\n"
  " 2 9 0  10 1\n"
  " 2 3 0  10 0\n"
  " 2 6 0  10 6\n"
  " 3 4 0   5 1\n"
  " 3 5 0  10 4\n"
  " 4 7 0  10 5\n"
  " 5 6 0  20 2\n"
  " 5 7 0  15 7\n"
  " 6 8 0  10 8\n"
  " 7 8 0  15 9\n"
  "\n"






On Thu, Jul 1, 2010 at 6:38 AM, Matthew Galati <magh at lehigh.edu> wrote:

>
> The first and maybe the fastest option is to contribute such an
>> extension by yourself. We are more than happy to accept such a patch,
>> and will help in all possible way to prepare it, of course.
>>
>> If you can't do that, you/we can still persuade Peter (the main
>> developer of the NS code) to implement this feature. I guess this is
>> also a pretty viable option...
>>
>> Anyway, I created a ticket about this enhancement in the issue tracker,
>> see http://lemon.cs.elte.hu/trac/lemon/ticket/375
>>
>
>
> This would be great!
>
> 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.
>
> 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.
>
> 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.
>
> Thanks!
> Matt
>
>
>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20100707/40e0b04d/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Ahuja348_Case6b.pdf
Type: application/pdf
Size: 12704 bytes
Desc: not available
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20100707/40e0b04d/attachment.pdf>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: min_cost_flow_test.cc
Type: application/octet-stream
Size: 18465 bytes
Desc: not available
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20100707/40e0b04d/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: network_simplex.h
Type: application/octet-stream
Size: 54466 bytes
Desc: not available
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20100707/40e0b04d/attachment-0001.obj>