Questions tagged [subtour-elimination]

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

Filter by
Sorted by
Tagged with
0 votes
2 answers
70 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 &...
satk0's user avatar
  • 113
3 votes
0 answers
104 views

Number of Subtour Elimination Constraints for ATSP (DFJ Formulation)

In the DFJ formulation of the symmetric TSP, the subtour elimination constraints are typically written as: $$\sum_{\{i,j\} \in E: \ i \in S, j \notin S} x_{ij} \geq 2, \qquad \forall S \subset V, \; 3 ...
user11589's user avatar
5 votes
1 answer
183 views

Flow problem with side constraints: how to eliminate subtours?

I am working on a flow problem with side constraints. More specifically, I have a usual flow problem, with constraints that require some arcs to have exactly one unit of flow on them. This makes the ...
Kuifje's user avatar
  • 12.9k
7 votes
4 answers
706 views

Interpretation of a subtour elimination constraint in the TSP

I have a problem with understanding the following mathematical model of the TSP. Given that the TSP is: $$\min \sum_{i,j\in N} d_{i,j} \cdot x_{i,j}$$ subjected to: $$\begin{array}{rrrr}\sum_{j\in N}...
Snowflake's user avatar
  • 517
4 votes
1 answer
358 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, ...
A.Omidi's user avatar
  • 8,382
10 votes
1 answer
1k 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 ...
A.Omidi's user avatar
  • 8,382
14 votes
2 answers
376 views

Subtour elimination constraints - enumeration vs dynamically adding

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 ...
Albert Schrotenboer's user avatar