Category archives: AIMMS
The latest version of CPLEX, version 12.7, supports Benders decomposition. Benders decomposition is an approach to solve mathematical programming problems with a decomposable structure, including stochastic programming (SP) problems (it is also known as the L-shaped method). Computational results by IBM, see this slide show by Xavier Nodet, show that Benders decomposition is faster than traditional branch-and-cut for 5% of their nontrivial MIP models. That number might not seem impressive but for certain type of MIP problems Benders decomposition is much faster than other methods.
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: