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
518 stars 92 forks source link

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

Open rafidrm opened 3 years ago

rafidrm commented 3 years ago

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):