Tech Blog

Tips and Tricks for AIMMS Users

Category archives: Advanced

Solving a TSP using lazy constraints

Posted on May 26, 2015 by Leave a reply

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.

Continue reading »

This entry was posted in Advanced, CPLEX, GUROBI, Modeling on by .

Lazy Outer Approximation

Posted on August 20, 2012 by Leave a reply

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:

  • A cleaner and easier implementation; using less “tricks”.
  • It can also be used for problems with general integer variables.
  • It can be used by CPLEX and Gurobi.
  • Improved performance.
  • Continue reading »

    This entry was posted in Advanced, CPLEX, GMP, GUROBI, Technical on by .
  • Customer Reviews

    Read more AIMMS reviews
  • Review AIMMS on G2 Crowd
  • Recent Posts

  • Categories

  • CC