Wrong optimal solution - Random binpacking problem

[SaitoTsutomu]

Hello, I was solving a bin packing problem and encountered a bug-like situation.

How to reproduce

• Python: 3.11
• Python-MIP: 1.15.0
• CBC: may be 2.10 (can't confirm)

Building a Python environment

python3 -m venv venv
source venv/bin/activate
pip install mip==1.15.0 numpy==1.25.2

Case1: wrong answer

Optimal value is 55, but get 56.

from mip import Model, minimize, xsum
import numpy as np

nr, nc = 20, 55
sizes = [
   23, 26, 10, 26, 19, 20, 22, 15, 29, 11, 15, 17, 21, 18, 12, 10, 10,
   10, 12, 29, 13, 23, 25, 14, 15, 18, 15, 29, 13, 27, 25, 26, 12, 17,
   22, 19, 23, 23, 23, 11, 29, 21, 28, 15, 17, 27, 13, 11, 17, 23, 12,
   27, 16, 14, 20]

def solve(lb):
    m = Model(solver_name="CBC")
    x = m.add_var_tensor((nr, nc), "x", var_type="B")
    y = m.add_var("y", lb=lb)
    m.objective = minimize(y)
    for x_i in x:
        m += xsum(sizes * x_i) <= y
    for x_j in x.T:
        m += xsum(x_j) == 1
    m.verbose = 0
    m.optimize()
    assert m.status.value == 0  # OPTIMAL
    return x, m.objective_value

x, objval = solve(10)
print(objval)  # 56.0

Case2: wrong answer

x, objval = solve(9)
print(objval)  # 63.0

63 is not 55.

Confirm optimal

Optimal is 55.

opt = np.zeros((nr, nc))
opt[[0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7,
     8, 8, 9, 9, 9, 10, 10, 10, 11, 11, 11, 12, 12, 12,
     13, 13, 13, 14, 14, 14, 15, 15, 15, 16, 16, 16, 16,
     17, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19],
    [8, 1, 19, 3, 27, 31, 40, 22, 42, 29, 45, 51, 30, 0,
     21, 36, 37, 38, 49, 6, 2, 34, 12, 14, 41, 5, 23, 54,
     4, 52, 35, 13, 25, 11, 33, 44, 48, 7, 10, 24, 26, 43,
     15, 53, 20, 28, 46, 18, 32, 50, 9, 39, 47, 16, 17]] = 1

assert opt.shape == x.shape
for x_i in opt:
    assert sum(sizes * x_i) <= 55

for x_j in opt.T:
    assert sum(x_j) == 1

[jjhforrest]

Looks as if the error is in the interface to Cbc or an old and bad version of Cbc. If I write out the model as an mps file and give it Cbc, I get an answer of 52. This is the case if I set lb to 3,....,10. If I run using m.optimize() for 3,,,,,10 I get 56,63,58,57,59,58,58,58 all of which are non-optimal answers.

I don't know how to create a debugging version of Cbc (with Python-MIP) to investigate further.

[SaitoTsutomu]

@jjhforrest Thank you very much. It appears that the Linux version of CBC that accompanies Python-MIP is incorrect.