# Controlling the constraint execution sequence in docplex

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

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:

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)

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)


First of all, calling add_lazy_constraint in your code is useless. The list of constraints that this establishes is never used. This is something that comes from the original lazy constraint callback example but is now unused in your updated code.
• I don't want the MTZ constraint but want to assign a distance to each node selected from the source (which becomes similar to MTZ). Another Idea that I was thinking that in callback I can check if there is no sub tour or not, then a simple If else statement can be used to add these constraints. Like If there is a sub tour i.e., (n < len(self.set_n)) then I will add sub tour violated constraint else add MTZ constraint.