### Category archives: Advanced

### Solving a TSP using lazy constraints

Posted on May 26, 2015 by Marcel HuntingLeave a replyThe 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.

### Lazy Outer Approximation

Posted on August 20, 2012 by Marcel HuntingLeave a replyA 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: