使用惰性约束回调实现TSP [英] Implementing TSP with Lazy constraint callback

问题描述

我正在尝试使用Lazy约束回调进行TSP。从此处和此处，我尝试使用链接中的代码并能够添加回叫功能。现在，我在 add_lazy_constraints 中苦苦挣扎。

I am trying to TSP with Lazy constraint callback. From Answer given here and here, I have tried to use the code from the links and was able to add the call back function. Now I am struggling with add_lazy_constraints.

这是我当前的代码：这是一个9节点TSP。 p>

Here is my current code: It is a 9 Node TSP.

import docplex.mp.model as cpx
from cplex.callbacks import LazyConstraintCallback
from docplex.mp.callbacks.cb_mixin import *


class DOLazyCallback(ConstraintCallbackMixin, LazyConstraintCallback):
    def __init__(self, env):
        LazyConstraintCallback.__init__(self, env)
        ConstraintCallbackMixin.__init__(self)
        self.nb_lazy_cts = 0

    def add_lazy_constraints(self, cts):
        self.register_constraints(cts)

    @print_called('--> lazy constraint callback called: #{0}')
    def __call__(self):
        # fetch variable values into a solution
        sol = self.make_solution()
        # for each lazy constraint, check whether it is verified,
        unsats = self.get_cpx_unsatisfied_cts(self.cts, sol, tolerance=1e-6)
        for ct, cpx_lhs, sense, cpx_rhs in unsats:
            self.add(cpx_lhs, sense, cpx_rhs)
            self.nb_lazy_cts += 1
            print('  -- new lazy constraint[{0}]: {1!s}'.format(self.nb_lazy_cts, ct))


DST = [[0, 0.238, 0.608, 0.5442, 0.6097, 1.2337, 0.5574, 0.8691, 1.3394],
       [0.238, 0, 0.37, 0.6694, 0.6039, 0.9957, 0.6826, 0.8633, 1.23],
       [0.608, 0.37, 0, 1.0394, 0.9739, 0.6257, 1.0526, 1.2333, 0.860],
       [0.5442, 0.6694, 1.0394, 0, 0.0655, 0.903, 0.0132, 0.3249, 0.7952],
       [0.6097, 0.6039, 0.9739, 0.0655, 0, 0.8375, 0.0787, 0.2594, 0.7297],
       [1.2337, 0.9957, 0.6257, 0.903, 0.8375, 0, 0.9162, 0.7046, 0.2343],
       [0.5574, 0.6826, 1.0526, 0.0132, 0.0787, 0.9162, 0, 0.3381, 0.8084],
       [0.8691, 0.8633, 1.2333, 0.3249, 0.2594, 0.7046, 0.3381, 0, 0.4703],
       [1.3394, 1.23, 0.860, 0.7952, 0.7297, 0.2343, 0.8084, 0.4703, 0]]

n = 9

set_n = range(9)
opt_model = cpx.Model(name="MIP Model")

x = {(i, j): opt_model.binary_var(name="x_{0}_{1}".format(i, j)) for i in set_n for j in set_n if not i == j}

objective = opt_model.sum(DST[i][j] * x[i, j] for i in set_n for j in set_n if not i == j)

# one incoming edge one outgoing edge
for i in set_n:
    xp = opt_model.sum(x[j, i] for j in set_n if not i == j) - opt_model.sum(x[i, k] for k in set_n if not i == k)
    opt_model.add_constraint(xp == 0)

for j in set_n:
    opt_model.add_constraint(opt_model.sum(x[i, j] for i in set_n if not i == j) == 1)

lazyct_cb = opt_model.register_callback(DOLazyCallback)

lazyct_cb.add_lazy_constraints( ?? WHAT TO ADD HERE ?? )


opt_model.lazy_callback = lazyct_cb

url = "URLL"
api = "APII"

#opt_model.parameters.mip.tolerances.mipgap = 0
opt_model.minimize(objective)

print(opt_model.print_information())

solv = opt_model.solve(url=url, key=api)
print(solv.solve_status)
print(solv.solve_details)

推荐答案

我不认为您想提前致电 add_lazy_constraints 。如果这样做了，则可以直接将懒惰约束添加到模型中。

I don't think you want to call add_lazy_constraints beforehand. If you did this, then you could just add the lazy constraints directly to the model.

相反，您需要在回调函数中使用一些代码来分隔约束。根据 sol 中的值，您会发现违反的子巡回消除约束并将其添加。

Instead you want some code in your callback that separates the constraints. Based on the values in sol you find a violated subtour elimination constraint and add it.

这篇关于使用惰性约束回调实现TSP的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！