An outer approximation based branch and cut algorithm for convex 0-1 MINLP problems
File(s)DTR00-6.pdf (258.22 KB)
Technical report
Author(s)
Akrotirianankis, Ioannis
Maros, Istvan
Rustem, Berc
Type
Report
Abstract
A branch and cut algorithm is developed for solving 0-1 MINLP problems. The algorithm integrates Branch and Bound, Outer Approximation and Gomory Cutting Planes. Only the initial Mixed Integer Linear Programming (MILP) master problem is considered. At integer solutions Nonlinear Programming (NLP) problems are solved, using a primal-dual interior point algorithm. The objective and constraints are linearized at the optimum solution of those NLP problems and the linearizations are added to all the unsolved nodes of the enumerations tree. Also, Gomory cutting planes, which are valid throughout the tree, are generated at selected nodes. These cuts help the algorithm to locate integer solutions quickly and consequently improve the linear approximation of the objective and constraints, held at the unsolved nodes of the tree. Numerical results show that the addition of Gomory cuts can reduce the number of nodes in the enumeration tree.
Date Issued
2000-06-01
Citation
Departmental Technical Report: 2000/6, 2000, pp.1-21
Start Page
1
End Page
21
Journal / Book Title
Departmental Technical Report: 2000/6
Copyright Statement
© 2000 The Author(s). This report is available open access under a CC-BY-NC-ND (https://creativecommons.org/licenses/by-nc-nd/4.0/)
Place of Publication
Department of Computing, Imperial College London
Publication Status
Published