Questions tagged [subtour-elimination]
For questions related to constraints intended to eliminate subtours (disconnected tours) in routing problems.
4
questions
7
votes
4
answers
364
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}...
- 507
4
votes
1
answer
205
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, ...
- 6,114
10
votes
1
answer
820
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 ...
- 6,114
14
votes
2
answers
280
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 ...
- 1,839