使用 Lazy 约束回调实现 TSP
Implementing TSP with Lazy constraint callback
我正在尝试使用惰性约束回调进行 TSP。从给出的答案 and here,我尝试使用链接中的代码并能够添加回调函数。现在我正在为 add_lazy_constraints
.
苦苦挣扎
这是我当前的代码:它是一个 9 节点 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
。如果你这样做,那么你可以直接将惰性约束添加到模型中。
相反,您需要在回调中使用一些代码来分隔约束。根据 sol
中的值,您找到一个违反的 subtour 消除约束并添加它。
我正在尝试使用惰性约束回调进行 TSP。从给出的答案 add_lazy_constraints
.
这是我当前的代码:它是一个 9 节点 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
。如果你这样做,那么你可以直接将惰性约束添加到模型中。
相反,您需要在回调中使用一些代码来分隔约束。根据 sol
中的值,您找到一个违反的 subtour 消除约束并添加它。