Implementing TSP with Lazy constraint callback

Question

I am trying to TSP with Lazy constraint callback. From Answer given here and here, I have tried to use the code from the links and was able to add the call back function. Now I am struggling with add_lazy_constraints.

Here is my current code: It is a 9 Node TSP.

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)

Daniel Junglas · Accepted Answer · 2020-03-05T14:07:39.720

3

I don't think you want to call add_lazy_constraints beforehand. If you did this, then you could just add the lazy constraints directly to the model.

Instead you want some code in your callback that separates the constraints. Based on the values in sol you find a violated subtour elimination constraint and add it.

edited Mar 05 '20 at 14:07

answered Mar 05 '20 at 14:01

Daniel Junglas

5,830
1
5
22

Ok so inside `def __call__(self):`, I need to somehow get the values of the binary variable `x` and check if there is a sub route if so then add a constraint that eliminates it. Am I correct? – ooo Mar 05 '20 at 14:17
By using Following code `for i, v in enumerate(self.get_values()): if v > 0: print(self.index_to_var(i), v)` inside `def __call__(self):` I got `x_0_1 1.0 x_1_2 1.0 x_2_0 1.0 x_3_4 1.0 x_4_6 1.0 x_5_7 1.0 x_6_3 1.0 x_7_8 1.0 x_8_5 1.0` I can clearly see cycles `5-7-8-5`, `0-1-2-0`, `3-4-6-3`, Now How can I enforce to eliminate these cycle. Do I need some algorithm to find the cycle and get their nodes and add constraint . Next inside `def __call__(self):` I can add `self.add_lazy_constraints()`, but what to write Inside it, i.e., how to access variable`x` – ooo Mar 05 '20 at 15:01
Correct, once you have the solution vector, you need to derive a violated constraint from it. You can take a look at `opl/examples/opl/models/TravelingSalesmanProblem` which ships with CPLEX and contains an example for separating subtours in OPL. Once you have found a subtour, you can construct a a subtour elimination constraint for this subtour, feed it as a singleton list into `get_cpx_unsatisfied_cts` and then proceed as in the example you already quoted. – Daniel Junglas Mar 06 '20 at 11:26
I executed this line `unsats = self.get_cpx_unsatisfied_cts(self.cts, sol, tolerance=1e-6)` and `unsats` is empy array, since I didn't have any unsatisfied lazy constraint that make sense, but let say I know there is a sub tour between node `5-7-8-5`. I can't figure out How can I add this constraint inside `get_cpx_unsatisfied_cts`, My constraint is like `x[5,7]+x[7,8]+x[8,5] <= 2`. How can I add this ? – ooo Mar 07 '20 at 06:12
I can see the values of variables using `self.get_values()` but how to write something like this `x[5,7]+x[7,8]+x[8,5] <= 2` once I get this constraint written I can easily add it using `self.add_lazy_constraints` (I think so). Can you explain with a small piece of code example? – ooo Mar 07 '20 at 06:22
You have to create a dictionary that maps between variables indices and variables objects. As you already figured, you can get the values using `x = self.get_values()`. Then you can do `value = { self.index_to_var(j) : a for j, a in enumerate(x) }`. The `value` dictionary can now be index by the variables with which you built your model. So find a subtour with these variables. From this build a constraints `c` and call `self.get_cpx_unsatisfied_cts([c], sol)`. That should give you the constraint in CPLEX form. – Daniel Junglas Mar 09 '20 at 07:06
2

I created an example for TSP with lazy constraints here: https://github.com/djunglas/cplex_code_examples/blob/master/docplex/tsp.py – Daniel Junglas Mar 09 '20 at 08:23
I have another problem here https://or.stackexchange.com/questions/3667/tsp-subtour-elimination-with-multiple-formulations , I want to add a constraint which is similar to MTZ, but with callback method, I am not sure what is the best place to add it, I have tried adding it as a lazy constraint, adding it inside the callback method and as a user cut. (Since I can't add it as a normal constraint) But not sure what is correct or best, although all work on a small example of 9 nodes. – ooo Mar 11 '20 at 13:15

Implementing TSP with Lazy constraint callback

1 Answers1

Linked