I have tried to implement my question asked here with the help of Github code link.
Below is the linearized version of the MTZ like constraint as per the answer given here. Constraints below assign distance traveled from source to each node in the path.
$$DS_{j} \geq DS_{i} + d_{i,j} - M \times (1 - b_{i,j})$$
$$DS_{j} \leq DS_{i} + d_{i,j} + M \times (1 - b_{i,j})$$
My code:
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_from_vars(self.x.values())
history = [0]
j = 0
while 1:
for i in self.set_n:
if not i == j and sol.get_value(self.x[j, i]) == 1.0:
history.append(i)
j = i
break
if j == 0:
break
print(history)
n = len(history) - 1
if n < len(self.set_n):
tour = 0
for i, v in enumerate(history):
if not i == n:
tour += self.x[v, history[i + 1]]
ct = tour <= n - 1
cst = [ct]
unsats = self.get_cpx_unsatisfied_cts(cst, sol, tolerance=0)
for ct, cpx_lhs, sense, cpx_rhs in unsats:
print('Add violated subtour')
self.add(cpx_lhs, sense, cpx_rhs)
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}
D = {i: opt_model.continuous_var(name="D_{0}".format(i)) for i in set_n}
objective = opt_model.sum(DST[i][j] * x[i, j] for i in set_n for j in set_n if not i == j)
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)
opt_model.add_constraint(D[0] == 0)
M = 100
for i in set_n:
for j in set_n:
if not i == j and not i == 0:
opt_model.add_constraint(D[i] <= D[j] + DST[i][j] + M * (1 - x[j, i]))
opt_model.add_constraint(D[i] >= D[j] + DST[i][j] - M * (1 - x[j, i]))
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.x = x
lazyct_cb.set_n = set_n
lazyct_cb.D = D
lazyct_cb.DST = DST
lazyct_cb.x = x
opt_model.lazy_callback = lazyct_cb
opt_model.parameters.mip.tolerances.mipgap = 0
opt_model.minimize(objective)
solv = opt_model.solve()
My aspected behavior from the code is that first, it should eliminate the sub tour by using the callback only, then it should run the above MTZ like a constraint to assign distance.
NOTE: There are other constraints that can change the path chosen. They should also run after the sub tour is eliminated (I think so).
One thing I am sure of is that I can't add MTZ like constraint as a normal constraint using add_constraint
since it also eliminated sub tour.
I tried adding MTZ like constraint using add_user_cut_constraint
, add_lazy_constraint
, register_constraint
(register_constraint
is added inside the callback), for a small example of 9 node TSP. All of the above methods give the correct results, but I am not sure what is the correct method.
I am highly confident about register_constraint
as it adds constraint when the callback is called, but not sure that every time callback is called keep adding the same constraint, again and again, is a good idea or not.
There is also another method in which I can add this MTZ like constraint inside callback using method get_cpx_unsatisfied_cts
.
(pseudocode):
ct = tour <= n - 1
cst = [ct]
cst.append(D[i] <= D[j] + DST[i][j] + M * (1 - x[j, i]))
cst.append(D[i] >= D[j] + DST[i][j] - M * (1 - x[j, i]))
unsats = self.get_cpx_unsatisfied_cts(cst, sol, tolerance=0)