coin-or / coin-or/python-mip

Wrong results

Open
#337 0 comments 0 reactions 0 assignees View on GitHub
bug cbc
Dominant language
Linear Programming
Stars
600
Forks
108
PR merge metrics
No merged PRs in 30d

Description

**Describe the bug**

I constructed an integer program modeling a number partitioning problem (partition a given set of numbers into two bins such that the largest bin sum is minimized), and the results are wrong.

**To Reproduce**

I attach the output of `model.write` in LP format:
[issue17b.lp.txt](https://github.com/coin-or/python-mip/files/10835608/issue17b.lp.txt)

```
Minimize
OBJROW: 152 item00152_in_bin1 + 489 item00489_in_bin1 + 2178 item02178_in_bin1 + 2518 item02518_in_bin1 + 3212 item03212_in_bin1 + 3270 item03270_in_bin1 + 3410 item03410_in_bin1 + 4979 item04979_in_bin1 + 5984 item05984_in_bin1 + 7183 item07183_in_bin1
+ 7740 item07740_in_bin1 + 7862 item07862_in_bin1 + 8519 item08519_in_bin1 + 8798 item08798_in_bin1 + 9948 item09948_in_bin1
Subject To
constr(0): item00152_in_bin0 >= 0
constr(1): item00489_in_bin0 >= 0
constr(2): item02178_in_bin0 >= 0
constr(3): item02518_in_bin0 >= 0
constr(4): item03212_in_bin0 >= 0
constr(5): item03270_in_bin0 >= 0
constr(6): item03410_in_bin0 >= 0
constr(7): item04979_in_bin0 >= 0
constr(8): item05984_in_bin0 >= 0
constr(9): item07183_in_bin0 >= 0
constr(10): item07740_in_bin0 >= 0
constr(11): item07862_in_bin0 >= 0
constr(12): item08519_in_bin0 >= 0
constr(13): item08798_in_bin0 >= 0
constr(14): item09948_in_bin0 >= 0
constr(15): item00152_in_bin1 >= 0
constr(16): item00489_in_bin1 >= 0
constr(17): item02178_in_bin1 >= 0
constr(18): item02518_in_bin1 >= 0
constr(19): item03212_in_bin1 >= 0
constr(20): item03270_in_bin1 >= 0
constr(21): item03410_in_bin1 >= 0
constr(22): item04979_in_bin1 >= 0
constr(23): item05984_in_bin1 >= 0
constr(24): item07183_in_bin1 >= 0
constr(25): item07740_in_bin1 >= 0
constr(26): item07862_in_bin1 >= 0
constr(27): item08519_in_bin1 >= 0
constr(28): item08798_in_bin1 >= 0
constr(29): item09948_in_bin1 >= 0
constr(30): item00152_in_bin0 + item00152_in_bin1 = 1
constr(31): item00489_in_bin0 + item00489_in_bin1 = 1
constr(32): item02178_in_bin0 + item02178_in_bin1 = 1
constr(33): item02518_in_bin0 + item02518_in_bin1 = 1
constr(34): item03212_in_bin0 + item03212_in_bin1 = 1
constr(35): item03270_in_bin0 + item03270_in_bin1 = 1
constr(36): item03410_in_bin0 + item03410_in_bin1 = 1
constr(37): item04979_in_bin0 + item04979_in_bin1 = 1
constr(38): item05984_in_bin0 + item05984_in_bin1 = 1
constr(39): item07183_in_bin0 + item07183_in_bin1 = 1
constr(40): item07740_in_bin0 + item07740_in_bin1 = 1
constr(41): item07862_in_bin0 + item07862_in_bin1 = 1
constr(42): item08519_in_bin0 + item08519_in_bin1 = 1
constr(43): item08798_in_bin0 + item08798_in_bin1 = 1
constr(44): item09948_in_bin0 + item09948_in_bin1 = 1
constr(45): -152 item00152_in_bin0 + 152 item00152_in_bin1 -489 item00489_in_bin0 + 489 item00489_in_bin1 -2178 item02178_in_bin0 + 2178 item02178_in_bin1 -2518 item02518_in_bin0 + 2518 item02518_in_bin1 -3212 item03212_in_bin0 + 3212 item03212_in_bin1
-3270 item03270_in_bin0 + 3270 item03270_in_bin1 -3410 item03410_in_bin0 + 3410 item03410_in_bin1 -4979 item04979_in_bin0 + 4979 item04979_in_bin1 -5984 item05984_in_bin0 + 5984 item05984_in_bin1 -7183 item07183_in_bin0 + 7183 item07183_in_bin1
-7740 item07740_in_bin0 + 7740 item07740_in_bin1 -7862 item07862_in_bin0 + 7862 item07862_in_bin1 -8519 item08519_in_bin0 + 8519 item08519_in_bin1 -8798 item08798_in_bin0 + 8798 item08798_in_bin1 -9948 item09948_in_bin0 + 9948 item09948_in_bin1
>= -0
Bounds
Integers
item00152_in_bin0 item00152_in_bin1 item00489_in_bin0 item00489_in_bin1 item02178_in_bin0 item02178_in_bin1 item02518_in_bin0 item02518_in_bin1 item03212_in_bin0 item03212_in_bin1
item03270_in_bin0 item03270_in_bin1 item03410_in_bin0 item03410_in_bin1 item04979_in_bin0 item04979_in_bin1 item05984_in_bin0 item05984_in_bin1 item07183_in_bin0 item07183_in_bin1
item07740_in_bin0 item07740_in_bin1 item07862_in_bin0 item07862_in_bin1 item08519_in_bin0 item08519_in_bin1 item08798_in_bin0 item08798_in_bin1 item09948_in_bin0 item09948_in_bin1
End
```

Here is the solution I get, with value 38123:
```
item00152_in_bin0 = 0
item00489_in_bin0 = 0
item02178_in_bin0 = 0
item02518_in_bin0 = 1
item03212_in_bin0 = 0
item03270_in_bin0 = 0
item03410_in_bin0 = 1
item04979_in_bin0 = 0
item05984_in_bin0 = 1
item07183_in_bin0 = 0
item07740_in_bin0 = 1
item07862_in_bin0 = 0
item08519_in_bin0 = 1
item08798_in_bin0 = 0
item09948_in_bin0 = 1

item00152_in_bin1 = 1
item00489_in_bin1 = 1
item02178_in_bin1 = 1
item02518_in_bin1 = 0
item03212_in_bin1 = 1
item03270_in_bin1 = 1
item03410_in_bin1 = 0
item04979_in_bin1 = 1
item05984_in_bin1 = 0
item07183_in_bin1 = 1
item07740_in_bin1 = 0
item07862_in_bin1 = 1
item08519_in_bin1 = 0
item08798_in_bin1 = 1
item09948_in_bin1 = 0
```

**Expected behavior**
There is another solution, with value 38122:

```
item00152_in_bin0 = 1
item00489_in_bin0 = 1
item02178_in_bin0 = 0
item02518_in_bin0 = 0
item03212_in_bin0 = 0
item03270_in_bin0 = 0
item03410_in_bin0 = 1
item04979_in_bin0 = 0
item05984_in_bin0 = 0
item07183_in_bin0 = 0
item07740_in_bin0 = 1
item07862_in_bin0 = 1
item08519_in_bin0 = 1
item08798_in_bin0 = 0
item09948_in_bin0 = 1

item00152_in_bin1 = 0
item00489_in_bin1 = 0
item02178_in_bin1 = 1
item02518_in_bin1 = 1
item03212_in_bin1 = 1
item03270_in_bin1 = 1
item03410_in_bin1 = 0
item04979_in_bin1 = 1
item05984_in_bin1 = 1
item07183_in_bin1 = 1
item07740_in_bin1 = 0
item07862_in_bin1 = 0
item08519_in_bin1 = 0
item08798_in_bin1 = 1
item09948_in_bin1 = 0
```

**Desktop (please complete the following information):**
- Windows 11 22H2
- Python version: 3.10.2
- Python-MIP version (we recommend you to test with the latest version): 1.14.0

**Additional context**
Note that the alternative solution was derived by solving the same problem but with a different order of variables.

[issue17a.lp.txt](https://github.com/coin-or/python-mip/files/10835621/issue17a.lp.txt)

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.