Opened 9 years ago

Closed 9 years ago

## #509 closed defect (invalid)

# Unstable NetworkSimplex Algorithm

Reported by: | Chassein | Owned by: | Alpar Juttner |
---|---|---|---|

Priority: | major | Milestone: | LEMON 1.4 release |

Component: | core | Version: | release branch 1.3 |

Keywords: | Cc: | ||

Revision id: |

### Description

Hey everyone, i was using the NetworkSimplex? algorithm from Lemon to solve min cost flow Problems. I encountered the following problem. I have two different objective functions (c_1 and c_2) for the same minimum cost flow Problem (same graph, same supply, same bounds). Let x_i be the solution that I obtain by calling the NetworkSimplex? with the objective function c_i. (i=1,2) My problem is that x_2 performs about 2% better under objective function c_1 as x_1 does! (c_1(x_2) < c_1(x_1)). Note that c_1 and c_2 are very similar and defined by double values. I cannot solve the problem by making c_1 and c_2 integral after scaling them. Is this 2% inaccuracy just a normal unavoidable effect or is there something I can do to get more accuracy? I'm using Version 1.3.1.

Best Regards Andre Chassein

### Change History (4)

### comment:1 Changed 9 years ago by

### comment:2 Changed 9 years ago by

You can also try another min-cost flow algorithm provided by LEMON. CapacityScaling should be the most stable and accurate in case of non-integer costs. Moreover, please note that the other algorithms actually does not support non-integer data. (They may handle them correctly, but it is not guaranteed.) See the warnings in their API documentation: http://lemon.cs.elte.hu/pub/doc/1.3/a00269.html http://lemon.cs.elte.hu/pub/doc/1.3/a00067.html

However, CapacityScaling can be significantly slower than NetworkSimplex.

### comment:3 Changed 9 years ago by

Hey everyone, I found out what was going wrong. The Problem was that my instances were infeasible. I didn't check that because the simplex returned an objective value. So, sorry for the unnecessary ticket.

The ticket can be deleted.

Regards, André Chassein

### comment:4 Changed 9 years ago by

Resolution: | → invalid |
---|---|

Status: | new → closed |

**Note:**See TracTickets for help on using tickets.

Replying to Chassein:

What does this mean? Is it impossible to scale the costs so that they will become integer or it is impossible to solve them using the integer costs (e.g. because of integer overflow)?