Tag Info

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 ...
• 2,352
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$ ...
• 13.6k

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 ...
• 6,657
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$.
• 33.1k

• 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: ...
• 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, ...
• 9,046

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