2
$\begingroup$

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)
$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – ooo
    Mar 13, 2020 at 12:51
  • $\begingroup$ Well, I am still not clear why you want subtour and MTZ-like constraints. The sole aim of both is to eliminate subtours, right? So if you use one type then the other type becomes redundant. Yes, you can check both types of constraints and inject whatever violated constraint you find. But I am not sure that this is more efficient than sticking to one type of constraints, you will have to try. $\endgroup$ Mar 13, 2020 at 13:48
  • $\begingroup$ In my original problem, there are several vehicles and based on their time of arrival at each node there are constraints that decide whether to take this path or not, so I need to assign time to each node for the respective vehicles, which is similar to assigning distance to each node. Now, what is best should I remove call back and be dependent on these MTZ like constraints or try to somehow add both to achieve fast execution. $\endgroup$
    – ooo
    Mar 13, 2020 at 14:26
  • $\begingroup$ If I understand correctly, then those MTZ-like constraints are a "must have". So the only question is whether subtour elimination constraints do buy you anything. I suggest to run experiments with and without them and see what runs faster. For these experiments you should use more than one single model. $\endgroup$ Mar 16, 2020 at 6:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.