### Category archives: AIMMS

### Benders Decomposition in CPLEX 12.7

Posted on December 13, 2016 by Marcel HuntingLeave a replyThe 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.

### 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: