Author Archives: Marcel Hunting
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.
The progress window, which can be opened by pressing CTRL-P, allows you to monitor AIMMS during compilation, execution and solving. For example, while solving a MIP problem, AIMMS will display the number of iterations and nodes, the best bound and the best solution in the progress window. So far, progress updates during a solve have been based on the number of iterations used by the solver. By default, the progress window is updated every 100 iterations. This frequency is controlled by the general solvers option Progress Solution.
The AIMMS webinar of August (2014) dealt with “Analyzing infeasible Problems in AIMMS”. In case you missed it, the recording can be found here. As shown in the webinar, one way to investigate an infeasible problem is by calculating an Irreducibly Inconsistent System (IIS). An IIS is a subset of all constraints and variables that contains an infeasibility. The “Irreducibly” part implies that the subset is as small as possible. Unfortunately, the IIS could only be calculated for linear (and quadratic) problems. So how about nonlinear problems?
Benders’ decomposition is an approach to solve complicated mathematical programming problems by splitting them into two, and thereby simplifying the solution process by (repeatedly) solving one master problem and one subproblem. If the problem contains integer variables then typically they become part of the master problem while the continuous variables become part of the subproblem. The classic approach of the Benders’ decomposition algorithm solves an alternating sequence of master problems and subproblems. Benders’ decomposition is mostly used for solving difficult MIP problems and stochastic programming problems.
We have developed a generic Benders’ decomposition module in AIMMS that is easy to use. A beta version of AIMMS 3.13 with Benders’ decomposition is now available for downloading. If you are interested to try it then we invite you to send an e-mail to our support.
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:
For solving Mixed Integer Nonlinear Programming (MINLP) problems AIMMS offers, besides the solvers BARON and KNITRO, the AIMMS Outer Approximation algorithm, or AOA for short.
There exist two versions of the AOA algorithm in AIMMS. The old version is available as a solver which calls the module OuterApproximation and was developed before GMP functionality was added to AIMMS. The new version uses GMP functions and has been implemented in the module GMPOuterApproximation. You can install this system module via Menu > Settings > Install System Module and select the GMP Outer Approximation Module to be installed. GMP-AOA is not a solver and cannot be called using the normal ‘solve’ statement. Instead you should use:
! First we must generate the GMP for our MathProgram. myGMP := GMP::Instance::Generate( myMP ) ; ! The GMP is passed as argument to the main procedure of GMP-AOA. GMPOuterApprox::DoOuterApproximation( myGMP );
An example can be found in this ZIP file.
There are several reasons why you should use GMP-AOA instead of old AOA. First, the GMP-AOA algorithm offers more possibilities to customize the algorithm to your needs, for example by using functions from the GMP library.
Second, the GMP version can be used in combination with the nonlinear presolver which may reduce the size of the model and tighten the variable bounds which likely help the AOA algorithm to find a better solution or improve its performance. From AIMMS 3.12 onwards GMP-AOA by default starts by calling the nonlinear presolver.
Third, for non-convex problems AOA might sometimes have difficulties in finding a good feasible solution. In that case it might help to combine the AOA with the multi-start algorithm. The way to do this has been explained in a white paper that describes GMP-AOA. This paper is available from our web site:
Old AOA cannot be combined with the nonlinear presolver nor the multi-start algorithm.
Note: In the special case that the MINLP problem contains only convex quadratic and/or second-order cone constraints also linear solvers like CPLEX or GUROBI can be used.