AIMMS Outer Approximation Algorithm for MINLP

Open solver approach

Outer approximation (see [DG86]) is a basic approach for solving Mixed-Integer NonLinear Programming (MINLP) models. The underlying algorithm is an interplay between two solvers, one for solving mixed-integer linear models and one for solving nonlinear models. Even though the standard outer approximation algorithm is provided with AIMMS, you as an algorithmic developer may want to customize the individual steps in order to obtain better performance and/or a better solution for your particular model.

The AIMMS Outer Approximation algorithm

The outer approximation algorithm in AIMMS is, therefore, provided as a customizable procedure written in the AIMMS language itself using functions and procedures provided by the GMP library (a white box solver), whereas most other outer approximation solvers are provided as a closed implementation (a black box solver). The outer approximation algorithm in AIMMS is implemented as a system module with the name GMP Outer Approximation. You can install this module using the Install System Module command in the AIMMS Settings menu. In the remainder of this chapter, we will refer to the outer approximation algorithm as AIMMS Outer Approximation (AOA).

Convex algorithm

Besides the basic algorithm, the AOA module also implements the Quesada-Grossmann algorithm (see [QG92]) which is designed to solve convex MINLP models. The basic algorithm can also be used to solve convex models but the Quesada-Grossmann algorithm is often more efficient.

This chapter

In this chapter you find the description of, and the motivation behind, the open approach to solving MINLP models based on outer approximation. We continue with a brief introduction to the problem statement and the basic algorithm. Next we explain how the AOA algorithm can be setup, followed by a detailed explanation of the parameters inside the AOA module that can be used to control the outer approximation algorithm. We then describe the Quesada-Grossmann algorithm for convex MINLP models. Next we describe an initial implementation of the basic solution algorithm using procedures in the AIMMS language is described. These procedures use functions that are especially designed to support the open approach. The chapter concludes with suggestions on additional ways to vary the individual steps of the overall algorithm in order to obtain customized versions of the outer approximation algorithm.