An outer-approximation algorithm for a class of mixed-integer nonlinear programs

Marco A. Duran, Ignacio E. Grossmann

Introduction

The 1986 work by Duran and Grossmann introduced the Outer-Approximation (OA) algorithm, which has since become a foundational method for solving Mixed-Integer Nonlinear Programming (MINLP) problems. MINLPs are characterized by the integration of discrete decision variables—often represented as binary choices—and nonlinear continuous functions. This combination makes them computationally demanding, as they require navigating both combinatorial complexity and non-convex continuous spaces. This paper provides a formal correction to the results of "Test Problem No. 4" from the original study, identifying a superior global optimum and clarifying the algorithm's performance on complex benchmarks.

The Outer-Approximation (OA) Framework

The OA algorithm operates by decomposing the MINLP into two distinct, alternating phases:

  1. Nonlinear Programming (NLP) Subproblems: By fixing the binary variables, the problem is reduced to a continuous nonlinear optimization. Solving this provides a local optimum and generates gradients used for the next phase.
  2. Mixed-Integer Linear Programming (MILP) Master Problems: Using the linearizations (outer-approximations) derived from the NLP step, the algorithm constructs a master problem. Solving this MILP yields a new set of binary variables that potentially improves the objective function.

This iterative process continues until the gap between the upper and lower bounds closes, ensuring convergence to the global optimum for convex problems.

Revised Benchmark: Test Problem No. 4

Test Problem No. 4 is a significant benchmark involving 25 binary variables and 5 continuous variables. In the original 1986 publication, a solution of $z^* = 7.7891$ was reported. However, subsequent analysis using more advanced hardware—specifically an IBM 3090/400 mainframe equipped with FPS Array Processors—revealed that the previously reported value was a local optimum.

The corrected global optimum is identified as $z^* = 8.0641$. The corresponding optimal continuous variables are $x^* = [2.0, 7.7924, 6.0556, 3.5732, 4.0]$, with a specific 25-bit configuration for the binary vector $y^*$.

Computational Performance and Sensitivity

The efficiency of the OA algorithm is highlighted by its rapid convergence. Despite the large search space of the 25-binary-variable problem, the algorithm reached the global optimum in only six iterations. The total CPU time required was 14.6 seconds, distributed as follows:

  • MILP Master Problems (MPSX): 10.8 seconds
  • NLP Subproblems (MINOS): 3.8 seconds

The data indicates that the majority of the computational effort (approximately 74%) was spent solving the MILP master problems, which is typical for problems with a high number of discrete variables. This correction also highlights how sensitive MINLP solutions are to the underlying software architecture and solver precision; moving to the IBM 3090/400 allowed for a more thorough exploration of the solution space than was previously possible.

Conclusion

The correction of Test Problem No. 4 underscores the sensitivity of MINLP solvers to starting points and computational precision. By leveraging refined solvers and more powerful architecture, the true global optimum was established. These results reaffirm the robustness and efficiency of the Outer-Approximation algorithm as a cornerstone of mixed-integer nonlinear optimization.

Summary updated

Abstract

An outer-approximation algorithm is presented for solving mixed-integer nonlinear programming problems of a particular class. Linearity of the integer (or discrete) variables, and convexity of the nonlinear functions involving continuous variables are the main features in the underlying mathematical structure. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the problems, and consists of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program. Convergence and optimality properties of the algorithm are presented, as well as a general discussion on its implementation. Numerical results are reported for several example problems to illustrate the potential of the proposed algorithm for programs in the class addressed in this paper. Finally, a theoretical comparison with generalized Benders decomposition is presented on the lower bounds predicted by the relaxed master programs.
BibTeX
@article{duran1987outer,
  author = {Marco A. Duran and Ignacio E. Grossmann},
  title = {{An outer-approximation algorithm for a class of mixed-integer nonlinear programs}},
  journal = {Math. Program.},
  year = {1987},
  doi = {10.1007/bf02592081},
}
Figure