Eine Plattform für die Wissenschaft: Bauingenieurwesen, Architektur und Urbanistik
Eine Plattform für die Wissenschaft: Bauingenieurwesen, Architektur und Urbanistik
A disjunctive cut strengthening technique for convex MINLP
https://orcid.org/http://orcid.org/0000-0003-0299-5745
https://orcid.org/http://orcid.org/0000-0001-5612-5417
Generating polyhedral outer approximations and solving mixed-integer linear relaxations remains one of the main approaches for solving convex mixed-integer nonlinear programming (MINLP) problems. There are several algorithms based on this concept, and the efficiency is greatly affected by the tightness of the outer approximation. In this paper, we present a new framework for strengthening cutting planes of nonlinear convex constraints, to obtain tighter outer approximations. The strengthened cuts can give a tighter continuous relaxation and an overall tighter representation of the nonlinear constraints. The cuts are strengthened by analyzing disjunctive structures in the MINLP problem, and we present two types of strengthened cuts. The first type of cut is obtained by reducing the right-hand side value of the original cut, such that it forms the tightest generally valid inequality for a chosen disjunction. The second type of cut effectively uses individual right-hand side values for each term of the disjunction. We prove that both types of cuts are valid and that the second type of cut can dominate both the first type and the original cut. We use the cut strengthening in conjunction with the extended supporting hyperplane algorithm, and numerical results show that the strengthening can significantly reduce both the number of iterations and the time needed to solve convex MINLP problems.
A disjunctive cut strengthening technique for convex MINLP
https://orcid.org/http://orcid.org/0000-0003-0299-5745
https://orcid.org/http://orcid.org/0000-0001-5612-5417
Generating polyhedral outer approximations and solving mixed-integer linear relaxations remains one of the main approaches for solving convex mixed-integer nonlinear programming (MINLP) problems. There are several algorithms based on this concept, and the efficiency is greatly affected by the tightness of the outer approximation. In this paper, we present a new framework for strengthening cutting planes of nonlinear convex constraints, to obtain tighter outer approximations. The strengthened cuts can give a tighter continuous relaxation and an overall tighter representation of the nonlinear constraints. The cuts are strengthened by analyzing disjunctive structures in the MINLP problem, and we present two types of strengthened cuts. The first type of cut is obtained by reducing the right-hand side value of the original cut, such that it forms the tightest generally valid inequality for a chosen disjunction. The second type of cut effectively uses individual right-hand side values for each term of the disjunction. We prove that both types of cuts are valid and that the second type of cut can dominate both the first type and the original cut. We use the cut strengthening in conjunction with the extended supporting hyperplane algorithm, and numerical results show that the strengthening can significantly reduce both the number of iterations and the time needed to solve convex MINLP problems.
A disjunctive cut strengthening technique for convex MINLP
https://orcid.org/http://orcid.org/0000-0003-0299-5745
https://orcid.org/http://orcid.org/0000-0001-5612-5417
Generating polyhedral outer approximations and solving mixed-integer linear relaxations remains one of the main approaches for solving convex mixed-integer nonlinear programming (MINLP) problems. There are several algorithms based on this concept, and the efficiency is greatly affected by the tightness of the outer approximation. In this paper, we present a new framework for strengthening cutting planes of nonlinear convex constraints, to obtain tighter outer approximations. The strengthened cuts can give a tighter continuous relaxation and an overall tighter representation of the nonlinear constraints. The cuts are strengthened by analyzing disjunctive structures in the MINLP problem, and we present two types of strengthened cuts. The first type of cut is obtained by reducing the right-hand side value of the original cut, such that it forms the tightest generally valid inequality for a chosen disjunction. The second type of cut effectively uses individual right-hand side values for each term of the disjunction. We prove that both types of cuts are valid and that the second type of cut can dominate both the first type and the original cut. We use the cut strengthening in conjunction with the extended supporting hyperplane algorithm, and numerical results show that the strengthening can significantly reduce both the number of iterations and the time needed to solve convex MINLP problems.
A disjunctive cut strengthening technique for convex MINLP
Optim Eng
Kronqvist, Jan (Autor:in) / Misener, Ruth (Autor:in)
Optimization and Engineering ; 22 ; 1315-1345
01.09.2021
31 pages
Aufsatz (Zeitschrift)
Elektronische Ressource
Englisch
On decomposition and multiobjective-based column and disjunctive cut generation for MINLP
| Springer Verlag | 2021
A review and comparison of solvers for convex MINLP
| Online Contents | 2018
MINLP approach to truss synthesis
| British Library Conference Proceedings | 2004
The MINLP approach to structural synthesis
| British Library Conference Proceedings | 2010