Category archives: Advanced
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.