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