search

coin-or / python-mip

Python-MIP: collection of Python tools for the modeling and solution of Mixed-Integer Linear programs
Eclipse Public License 2.0
516 stars 90 forks source link

m.optimize() returns OPTIMAL, but the found minimum is wrong. #210

Closed tooflesswulf closed 2 years ago

tooflesswulf commented 2 years ago

Describe the bug Calling m.optimize() returns OptimizationStatus.OPTIMAL, but the solution is not optimal.

To Reproduce I have a MIP problem defined here: problem.py.zip

Running the file gives me the output:

❯ python problem.py
STATUS: OptimizationStatus.OPTIMAL
Claimed minimum:   0.0407672349999999
----------MANUAL START RESULT----------
Actual minimum:   0.0

Within the file, the test_graph on line 82 can be replaced with another random graph, as long as the entries represent the minimum weighted path length between two vertices. I find the discrepancy between reported optimal and true optimal to still exist even when changing test_graph.

Expected behavior I expect that when m.optimize() returns Optimal, the objective is actually minimized.

Additional Info In the python file above, I test using a "trivial" problem that I know the answer must be zero. There are a couple other similar inputs for which I know the true minimum must be upper bounded by some value less than the optimization's output.

tuliotoffolo commented 2 years ago

Indeed, there is something wrong. We'll take a look at it to figure out what is happening.

PS: I was able to reproduce the error using our CBC interface. Gurobi's interface results in the expected objective value (0.0).

tkralphs commented 2 years ago

@tooflesswulf If you post an MPS file that replicates this in stand-alone Cbc to the Cbc project, then we can take a look.

sebheger commented 2 years ago

I have rerun the provided script with the latest master today. Looks fine.

STATUS: OptimizationStatus.OPTIMAL Claimed minimum: 0.0 ----------MANUAL START RESULT---------- Actual minimum: 0.0

Could be declared as fixed with next release.

sebheger commented 2 years ago

Fixed by https://github.com/coin-or/python-mip/milestone/2