Category archives: Advanced
The famous travelling salesman problem (TSP) deals with the following problem: given a list of cities and the distances between each pair of cities, a salesman has to find the shortest possible route to visit each city exactly once while returning to the origin city. One way to formulate the TSP is as follows:
min sum( (i,j), c(i,j)*x(i,j) ) (1) s.t. sum( i, x(i,j) + x(j,i) ) = 1 for all j x(i,j) binary for all i > j
Here x(i,j) equals 1 if the route from city i to city j is in the tour, and 0 otherwise. Note that this is the formulation for the symmetric TSP in which the distance from i to j equals the distance from j to i. This formulation is not complete as it allows for subtours. One way to exclude these subtours is by using subtour elimination constraints (SECs for short):
sum( (i,j) | i in S and not j in S, x(i,j) + x(j,i) ) >= 2 for all S, 1 < |S| < n
Here S is a subset of cities while n denotes the number of cities. This SEC enforces that at least one route is going from a city in set S to a city outside S.
A somewhat hidden functionality in AIMMS is the implementation of the Quesada and Grossmann algorithm for solving convex Mixed Integer Nonlinear Programming (MINLP) problems. For AIMMS 3.13 the implementation of this algorithm will use the lazy constraint callback function that was introduced in CPLEX 12.3 and Gurobi 5.0, and has several advantages over the old implementation: