Skip to main content
12 votes
Accepted

Subtour elimination constraints - enumeration vs dynamically adding

This has to depend on instance size. For a sports scheduling problem I worked on, it definitely made life easier to simply put in all the $|S| \le 3$ constraints (not exactly subtour, but very ...
Michael Trick's user avatar
10 votes
Accepted

Interpretation of a subtour elimination constraint in the TSP

These constraints are called Miller-Tucker-Zemlin (MTZ) constraints, you can find a lot of technical notes online. They impose that a node can only be visited once. You can think of the $u_i$ ...
Kuifje's user avatar
  • 13.6k
6 votes

How to remove or replace sub tour elimination constraints in the VRP variant models?

The inequalities you have included in your post are the so-called MTZ SEC's which are known to be very weak. That is, they do not provide a very tight approximation of the convex hull of integer ...
Sune's user avatar
  • 6,657
6 votes
Accepted

"GLPK: No Primal Feasible Solution" for Travelling Salesman Problem (Dantzig–Fulkerson–Johnson formulation)

The problem is indeed infeasible but becomes feasible if you omit the subtour57 constraint. For a tour on $6$ nodes, you need to use $6$ arcs, but that constraint allows only $5$.
RobPratt's user avatar
  • 33.1k
6 votes

Interpretation of a subtour elimination constraint in the TSP

To add another answer that focuses on why we use $\vert N\vert$ in the constraint: As @Pedrinho @Kuifje stated, the $u_i$ variables can be interpreted as the order of city $i$ in the tour. That is, $...
Sune's user avatar
  • 6,657
4 votes

Subtour elimination constraints - enumeration vs dynamically adding

In my experience it is helpful to add the smallest sub tour constraints directly into the model formulation. You should play a bit with the exact size but I commonly add subtour constraints up to 4 ...
Michiel uit het Broek's user avatar
4 votes

Interpretation of a subtour elimination constraint in the TSP

The constraint is nicely explained by @Kuifje. I want to add the following point concerning your comment regarding $|N|$. $|N|$ is only in place if $x_{ij} = 0$, so if there is no connecting edge ...
PeterD's user avatar
  • 1,706
3 votes
Accepted

Flow problem with side constraints: how to eliminate subtours?

Let $S$ be the set of arcs in a subtour of size $4$. No-good cuts are simple but weak: $$\sum_{(i,j)\in S} x_{ij} \le 4 - 1$$ Depending on the objective, you might get by with instead imposing no-...
RobPratt's user avatar
  • 33.1k
1 vote

"GLPK: No Primal Feasible Solution" for Travelling Salesman Problem (Dantzig–Fulkerson–Johnson formulation)

For python implementation using pyscipopt, you can refer as following: ...
ytsao's user avatar
  • 411
1 vote

The difference between subtour-elimination constraints in the symmetric and asymmetric TSP

I would like to add an answer by @Misha Lavrov: The MTZ constraints really need to know the direction of an edge in order to work. I have called them "timing constraints" when teaching, ...
A.Omidi's user avatar
  • 9,046

Only top scored, non community-wiki answers of a minimum length are eligible