Controlling the constraint execution sequence in docplex

Question

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)

Answer 1

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.

Next there seems to be a misconception: There is no "order" of constraints. All constraints are always enforced simultaneously. So as soon as you add MTZ constraints, subtour elimination constraints will no longer be violated. Since both types of constraints aim at eliminating subtours, you should probably settle for one of the two.