Can the callback function combine two check mechanism?(TSP subtour elimination + Bender's decomposition)

Answered

Jacob Jin

• January 25, 2022 16:55

Hello, I use callback function to optimize a MIP problem.

if where == GRB.Callback.MIPSOL:

    selected = gb.tuplelist((i, j) for i in range(N + 1) for j in range(N + 1)
                            if model.cbGetSolution(model.getVarByName('r_' + str(i) + str(j))) > 0.5)

    # find the shortest cycle in the selected edge list
    tour = self.subtour(selected)
    if len(tour) < N+1:
       # Add the subtour elimination constraint
       # ...
       # ...
    else:
       # Bender's cut
       LB = model.cbGet(GRB.Callback.MIPSOL_OBJBND)
       status, UB = sub_problem(z_1)
       if status == 3:
           # Add the feasibility cut 
           # ...
       if status == 2:
           if abs(UB - LB) >= 0.1:
               # Add the optimality cut
           elif len(tour) == N:
               model.terminate()
         

The logic is quite clear. However, it doesn't terminate according to the termination condition. It ends automatically and the length of tour is less than N. I don't know what's wrong with my code... And I want to know why the callback process would end by itself???

 

0

• 

  Jacob Jin

  • January 25, 2022 16:59

  

  

  

  I have verified that all the lazy constraints' formulations are correct。。。

  0
• 

  Jaromił Najman

  Gurobi Staff

  • January 31, 2022 14:35

  Hi Jacob,

  Could you briefly explain what is \(\texttt{N}\) in your code snippet?

  The case \(\texttt{len(tour) == N}\) cannot be reached because it always lands in \(\texttt{len(tour) < N+1}\).

  Best regards, 
  Jaromił

  0

Please sign in to leave a comment.