Solving mixed integer nonlinear programs by outer approximation.

*(English)*Zbl 0833.90088Summary: A wide range of optimization problems arising from engineering applications can be formulated as mixed integer nonlinear programming problems (MINLPs). M. A. Duran and I. E. Grossmann [Math. Program. 36, 307-339 (1986; Zbl 0619.90052)] suggest an outer approximation scheme for solving a class of MINLPs that are linear in the integer variables by a finite sequence of relaxed MILP master programs and NLP subproblems.

Their idea is generalized by treating nonlinearities in the integer variables directly, which allows a much wider class of problem to be tackled, including the case of pure INLPs. A new and more simple proof of finite termination is given and a rigorous treatment of infeasible NLP subproblems is presented which includes all the common methods for resolving infeasibility in Phase I.

The worst case performance of the outer approximation algorithm is investigated and an example is given for which it visits all integer assignments. This behaviour leads us to include curvature information into the relaxed MILP master problem, giving rise to a new quadratic outer approximation algorithm.

An alternative approach is considered to the difficulties caused by infeasibility in outer approximation, in which exact penalty functions are used to solve the NLP subproblems. It is possible to develop the theory in an elegant way for a large class of nonsmooth MINLPs based on the use of convex composite functions and subdifferentials, although an interpretation for the \(\ell_i\) norm is also given.

Their idea is generalized by treating nonlinearities in the integer variables directly, which allows a much wider class of problem to be tackled, including the case of pure INLPs. A new and more simple proof of finite termination is given and a rigorous treatment of infeasible NLP subproblems is presented which includes all the common methods for resolving infeasibility in Phase I.

The worst case performance of the outer approximation algorithm is investigated and an example is given for which it visits all integer assignments. This behaviour leads us to include curvature information into the relaxed MILP master problem, giving rise to a new quadratic outer approximation algorithm.

An alternative approach is considered to the difficulties caused by infeasibility in outer approximation, in which exact penalty functions are used to solve the NLP subproblems. It is possible to develop the theory in an elegant way for a large class of nonsmooth MINLPs based on the use of convex composite functions and subdifferentials, although an interpretation for the \(\ell_i\) norm is also given.

##### MSC:

90C11 | Mixed integer programming |

90C30 | Nonlinear programming |

90C10 | Integer programming |

49J52 | Nonsmooth analysis |

##### Keywords:

worst case performance; outer approximation algorithm; infeasibility; convex composite functions; subdifferentials
PDF
BibTeX
XML
Cite

\textit{R. Fletcher} and \textit{S. Leyffer}, Math. Program. 66, No. 3 (A), 327--349 (1994; Zbl 0833.90088)

Full Text:
DOI

##### References:

[1] | R. Breu and C.-A. Burdet, ”Branch-and-bound experiments in zero–one programming,”Mathematical Programming Study 2 (1974) 1–50. · Zbl 0358.90038 |

[2] | M. Duran and I.E. Grossmann, ”An outer-approximation algorithm for a class of Mixed Integer Nonlinear Programs,”Mathematical Programming 36 (1986) 307–339. · Zbl 0619.90052 · doi:10.1007/BF02592064 |

[3] | R. Fletcher,Practical Methods of Optimization (John Wiley, Chichester, 1987). · Zbl 0905.65002 |

[4] | O.E. Flippo et al., ”Duality and decomposition in general mathematical programming,” Econometric Institute, Report 8747/B, University of Rotterdam (1987). |

[5] | A.M. Geoffrion, ”Generalized Benders decomposition,”Journal of Optimization Theory and Applications 10 (1972) 237–262. · Zbl 0229.90024 · doi:10.1007/BF00934810 |

[6] | G.R. Kocis and I.E. Grossmann, ”Global optimization of nonconvex MINLP in process synthesis,”Industrial and Engineering Chemistry Research 27 (1988) 1407–1421. · doi:10.1021/ie00080a013 |

[7] | F. Körner, ”A new branching rule for the branch-and-bound algorithm for solving nonlinear integer programming problems,”BIT 28 (1988) 701–708. · Zbl 0657.65082 · doi:10.1007/BF01941144 |

[8] | R. Lazimy, ”Improved algorithm for mixed-integer quadratic programs and a computational study,”Mathematical Programming 32 (1985) 100–113. · Zbl 0591.90066 · doi:10.1007/BF01585661 |

[9] | J. Viswanathan and I.E. Grossmann, ”A combined penalty function and outer-approximation method for MINLP optimization,”Computers and Chemical Engineering 14 (1990) 769–782. · doi:10.1016/0098-1354(90)87085-4 |

[10] | X. Yuan, S. Zhang, L. Pibouleau and S. Domenech, ”Une méthode d’optimization non linéaire en variables mixtes pour la conception de procédés,”Operations Research 22/4 (1988) 331–346. · Zbl 0656.90071 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.