coin-or / coin-or/python-mip

Speeding up problem set-up

Open
#146 6 comments 2 reactions 0 assignees View on GitHub
mip
Dominant language
Linear Programming
Stars
600
Forks
108
PR merge metrics
No merged PRs in 30d

Description

This is more a suggestion than an actual bug.

I've been using python-mip and cvxpy on the same MI problems, and even though their actual problem-solving performances are usually the same (or even slightly better for python-mip), the problem set-up (defining the objective and the constraints) is much too slow with python-mip.

For instance, let's consider the following two implementations:

```python
A : np.ndarray of shape (2000, 3069)
d : np.ndarray of shape (3069,)

# python-mip
# the following block takes 11 seconds to run
model = mip.Model("disorders")
x = model.add_var_tensor(shape=(len(d),), name="x", var_type=mip.BINARY)
model.objective = mip.minimize(x.T @ d)
model += (A @ x == 1)

# this line takes 0.13s to run
status = model.optimize()

# cvxpy
# this blocks takes 0.14s
x = cp.Variable(shape=len(d), boolean=True)
obj = cvxpy.Minimize(d.T @ x)
constraints = [A @ x == 1]
prob = cvxpy.Problem(obj, constraints)
optimal = prob.solve()
```

It's quite a shame that python-mip is limited by such a non-central part of MIP-solving, that is, setting up the problem.
I used CProfile to figure out what's taking so much time when building the problem, and it seems that the repeated instance checks when multiplying a variable with a scalar are the culprits.

Maybe you could exploit the structured nature of `LinExprTensor` to have only one typecheck when multiplying then with arrays... or something like this.

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.