Реализация TSP с обратным вызовом Lazy - PullRequest
Новая
       93

Реализация TSP с обратным вызовом Lazy

0 голосов
/ 05 марта 2020

Я пытаюсь TSP с Lazy Callback Callback. Из ответа здесь и здесь я попытался использовать код из ссылок и смог добавить функцию обратного вызова. Сейчас я борюсь с add_lazy_constraints.

Вот мой текущий код: Это TSP с 9 узлами. 

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)

1 Ответ

2 голосов
/ 05 марта 2020

Не думаю, что вы хотите позвонить add_lazy_constraints заранее. Если вы сделали это, то могли бы просто добавить ленивые ограничения непосредственно в модель.

Вместо этого вам нужен код в вашем обратном вызове, который разделяет ограничения. Основываясь на значениях в sol, вы найдете нарушенное ограничение удаления подпочвы и добавите его.

...