coin-or / coin-or/python-mip

Adding Lazy Constraints leads to infeasible solution when it should not.

Open
#143 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 have a pathological example where I sequentially generate lazy constraints so that the problem is never solved.

If I generate the constraint each time, then the solver continues to search through the tree and adds constraints. However, if I randomly generate the constraint with some probability, then the solver terminates with infeasible in the root node.

**To Reproduce**

```
import mip
import numpy

class CutGenerator(mip.ConstrsGenerator):
def __init__(self, x, y):
self.counter = 0
self.x = x
self.y = y

def generate_constrs(self, model, depth=0, npass=0):
x = model.translate(self.x)
y = model.translate(self.y)
# If I introduce the constraint every time, then the model searches
# through the tree endlessly. If I randomly introduce the constraint
# then the model terminates and returns infeasible.
if np.random.rand() > 0.5:
model += x >= self.counter
print('adding constr x >= {}'.format(self.counter))
self.counter += 1

prob = mip.Model(solver_name=mip.CBC)

x = prob.add_var(var_type=mip.CONTINUOUS, name='x', lb=-10)
y = [prob.add_var(var_type=mip.BINARY, name='y{}'.format(i)) for i in range(3)]

prob.cuts = 0
prob.presolve = 0
prob.preprocess = 0
prob.objective = mip.minimize(x)
prob += mip.xsum(y) == 1

prob.lazy_constrs_generator = CutGenerator(x, y)
status = prob.optimize()
```

**Expected behavior**

I expect the solver to continue to search the tree, which it only does when cut generation is not random.

**Desktop (please complete the following information):**

- Operating System, version: Ubuntu
- Python version: 3.8
- Python-MIP version (we recommend you to test with the latest version): 1.12

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.