Lazy constraints for linear problem not generated

[christian2022]

Hi, I want to solve a linear program with lazy constraints. But the lazy constraint generator does not get called during optimize, although it should be - also for linear programs.

Example:

import mip

# Monkey patch extensions
mip.Model.get_value = lambda self, arg: (
    mip.xsum(coeff * var.x for var, coeff in arg.expr.items()) + arg.const if isinstance(arg, mip.LinExpr) else
    arg.x if isinstance(arg, mip.Var) else arg
)

mip.Model.translate_expr = lambda self, arg: (
    mip.xsum(coeff * self.translate(var) for var, coeff in arg.expr.items()) + arg.const if isinstance(arg, mip.LinExpr) else
    self.translate(arg) if isinstance(arg, (mip.Var, list, dict)) else arg
)

class cvx_cut_gen(mip.ConstrsGenerator):
    def __init__(self, func, func_grad, args, result):
        self.func = func
        self.func_grad = func_grad
        self.args = args
        self.result = result

    def get_cut(self, x_value=None, x=None):
        if x == None:
            x = self.args
        if x_value == None:
            x_value = [xi.x for xi in x]
        cut = self.result >= self.func(x_value) + mip.xsum(df_dxi * (xi - xi_value) for df_dxi, xi, xi_value in zip(self.func_grad(x_value), x, x_value))
        print("### cut at {}: {}".format(", ".join("{}".format(xi) for xi in x_value), cut))
        return cut

    def generate_constrs(self, model):
        x = [model.translate_expr(arg) for arg in self.args]
        x_value = [model.get_value(xi) for xi in x]
        cut = self.get_cut(x_value, x)
        print("### added cut because it's violated by {}".format(cut.violation))
        model.add_cut(cut)

def target(x):
    return 1 + sum((xi - 1.33)**2 for xi in x)

def target_gradient(x):
    return [2 * (xi - 1.33) for xi in x]

model = mip.Model()
dim = 3
x = [model.add_var(name="x_{}".format(i), lb=-10, ub=10) for i in range(dim)]
z = model.add_var(name="z", lb=-float('Inf'))

model.lazy_constrs_generator = cvx_cut_gen(target, target_gradient, x, z)
# add some initial cut otherwise presolver removes variables
model += model.lazy_constrs_generator.get_cut([xi.lb + (xi.ub - xi.lb) * 0.5 for xi in x])

model.objective = mip.minimize(z)

# FIXME: should call lazy_constr_generator, but doesn't
status = model.optimize()

print("### {}, minimum = {} at ({}), true value: {}".format(status, model.objective_value, ", ".join("{}".format(xi.x) for xi in x), target([xi.x for xi in x])))

# FIX: manually call generator until solved
epsilon = 1e-6
while abs(model.objective_value - target([xi.x for xi in x])) > epsilon * model.objective_value + epsilon:
    model.lazy_constrs_generator.generate_constrs(model)
    status = model.optimize()
    print("### {}, minimum = {} at ({}), true value: {}".format(status, model.objective_value, ", ".join("{}".format(xi.x) for xi in x), target([xi.x for xi in x])))

[h-g-s]

Hi,

Lazy constraints, by definition, are generated to remove integral solutions. To remove fractional solutions you should use the cut generators. Cut generators are called when the problem has integer variables defined and a fractional solution is found. You can also use both.

Cheers ​============================================================= Haroldo Gambini Santos Computing Department Universidade Federal de Ouro Preto - UFOP email: haroldo [at ] ufop.edu.br home/research page: www.decom.ufop.br/haroldo http://www.decom.ufop.br/haroldo/

It has long been an axiom of mine that the little things are infinitely the most important.

Em ter, 28 de abr de 2020 às 13:00, christian2022 notifications@github.com escreveu:

Hi, I want to solve a linear program with lazy constraints. But the lazy constraint generator does not get called during optimize, although it should be - also for linear programs.

Example:

import mip

Monkey patch extensions

mip.Model.get_value = lambda self, arg: ( mip.xsum(coeff * var.x for var, coeff in arg.expr.items()) + arg.const if isinstance(arg, mip.LinExpr) else arg.x if isinstance(arg, mip.Var) else arg )

mip.Model.translate_expr = lambda self, arg: ( mip.xsum(coeff * self.translate(var) for var, coeff in arg.expr.items()) + arg.const if isinstance(arg, mip.LinExpr) else self.translate(arg) if isinstance(arg, (mip.Var, list, dict)) else arg )

class cvx_cut_gen(mip.ConstrsGenerator): def init(self, func, func_grad, args, result): self.func = func self.func_grad = func_grad self.args = args self.result = result

def get_cut(self, x_value=None, x=None):
    if x == None:
        x = self.args
    if x_value == None:
        x_value = [xi.x for xi in x]
    cut = self.result >= self.func(x_value) + mip.xsum(df_dxi * 

(xi - xi_value) for df_dxi, xi, xi_value in zip(self.func_grad(x_value), x, x_value)) print("### cut at {}: {}".format(", ".join("{}".format(xi) for xi in x_value), cut)) return cut

def generate_constrs(self, model):
    x = [model.translate_expr(arg) for arg in self.args]
    x_value = [model.get_value(xi) for xi in x]
    cut = self.get_cut(x_value, x)
    print("### added cut because it's violated by 

{}".format(cut.violation)) model.add_cut(cut)

def target(x): return 1 + sum((xi - 1.33)**2 for xi in x)

def target_gradient(x): return [2 * (xi - 1.33) for xi in x]

model = mip.Model() dim = 3 x = [model.addvar(name="x{}".format(i), lb=-10, ub=10) for i in range(dim)] z = model.add_var(name="z", lb=-float('Inf'))

model.lazy_constrs_generator = cvx_cut_gen(target, target_gradient, x, z)

add some initial cut otherwise presolver removes variables

model += model.lazy_constrs_generator.get_cut([xi.lb + (xi.ub - xi.lb) * 0.5 for xi in x])

model.objective = mip.minimize(z)

FIXME: should call lazy_constr_generator, but doesn't

status = model.optimize()

print("### {}, minimum = {} at ({}), true value: {}".format(status, model.objective_value, ", ".join("{}".format(xi.x) for xi in x), target([xi.x for xi in x])))

FIX: manually call generator until solved

epsilon = 1e-6 while abs(model.objective_value - target([xi.x for xi in x])) > epsilon * model.objective_value + epsilon: model.lazy_constrs_generator.generate_constrs(model) status = model.optimize() print("### {}, minimum = {} at ({}), true value: {}".format(status, model.objective_value, ", ".join("{}".format(xi.x) for xi in x), target([xi.x for xi in x]))) — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/coin-or/python-mip/issues/95, or unsubscribe https://github.com/notifications/unsubscribe-auth/AB4VZOXFBH2BNX7J2N6WMYTRO4YVPANCNFSM4MTEBQYA.

[christian2022]

Hi Haroldo, thanks for your answer. I don't have any integer variables in my problem, but have a huge number of constraints describing my problem. If lazy constraint generator is not the way, then I manually need to add the violated constraints after each solve. Can I somehow make use of the outcomes of previous calls to solve or do I have to solve for each step from scratch? Cheers, Christian

[h-g-s]

Hi @christian2022 ,

Re-optimization of pure linear programs (no integer variables) is very efficient, so, something such as:

m = Model() """ include variables and part of constraints""" newConstraints = True while newConstraints: m.optimize() newConstraints = False """ check violated constraints , if found, add to m and set newConstraints to True"""

"""" at this point you should get a feasible solution """"