# Questions tagged [subtour-elimination]

For questions related to constraints intended to eliminate subtours (disconnected tours) in routing problems.

8 questions
Filter by
Sorted by
Tagged with
1 vote
41 views

### What reasons would cause lazy constraints to degrade the performances when reoptimizing with a different objective?

We are currently solving a hard MILP problem on optimality. Once it has been solved, several times (from 5 to 10 times), we change one coefficient of the objective function and reoptimize. Thus the ...
• 679
95 views

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

I have a problem with implementing the Dantzig–Fulkerson–Johnson formulation to solve the following Travelling Salesman Problem: \begin{bmatrix} M & 21 & 17 & 19 & 21 & 22\\ 26 &...
• 123
124 views

• 517
410 views

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

We know that there are lots of formulations for traveling salesman problem. Some of them are based on the directed graph (asymmetric) and others are based on the undirected graph (symmetric). Also, ...
• 8,960
2k views

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

In many of vehicle routing problems variant (VRP), which can be formulated using MIPs, to avoid creating sub tour, we need to use sub tour elimination constraints (SEC). One of the known SEC is (I ...
• 8,960
The classical constraints to prevent subtours in routing problems (i.e., to make sure every route is connected to a depot), are of the following form,  \sum_{(i,j) \in \delta(S)} x_{ij} \leq |S| - 1 ...