Towards the Solution of Mixed-Integer Nonlinear Optimization Problems using Simultaneous Convexification
Liers F, Martin A, Merkert M, Mertens N, Michaels D (2020)
Publication Language: English
Publication Type: Other publication type
Publication year: 2020
Pages Range: 36
URI: https://opus4.kobv.de/opus4-trr154/frontdoor/index/index/searchtype/latest/docId/303/start/0/rows/10
Abstract
Solving mixed-integer nonlinear optimization problems (MINLPs) to global optimality is extremely challenging. An important step for enabling their solution consists in the design of convex relaxations of the feasible set. Known solution approaches based on spatial branch-and-bound become more effective the tighter the used relaxations are. Relaxations are commonly established by convex underestimators, where each constraint function is considered separately. Instead, a considerably tighter relaxation can be found via so-called simultaneous convexification, where convex underestimators are derived for more than one constraint at a time. In this work, we present a global solution approach for solving mixed-integer nonlinear problems that uses simultaneous convexification. We introduce a separation method for the convex hull of constrained sets. It relies on determining the convex envelope of linear combinations of the constraints and on solving a nonsmooth convex problem. In particular, we apply the method to quadratic absolute value functions and derive their convex envelopes. The practicality of the proposed solution approach is demonstrated on several test instances from gas network optimization, where the method outperforms standard approaches that use separate convex relaxations.
Authors with CRIS profile
Frauke Liers-Bergmann
Professur für Optimization under Uncertainty & Data Analysis
Alexander Martin
Economics - Discrete Optimization - Mathematics (EDOM)
Related research project(s)
MIP techniques for equilibrium models with integer constraints (B07) (2018 - 2022)
TRR 154: Mathematical Modelling, Simulation and Optimisation Using the Example of Gas Networks (TRR 154)
July 1, 2018 - June 30, 2022
Decomposition methods for mixed-integer optimal control (A05) (2014 - 2018)
TRR 154: Mathematical Modelling, Simulation and Optimisation Using the Example of Gas Networks (TRR 154)
July 1, 2014 - July 1, 2017
Integrated graduate school research training group (MGK) (TRR 154)
TRR 154: Mathematical Modelling, Simulation and Optimisation Using the Example of Gas Networks (TRR 154)
July 1, 2014 - July 1, 2017
Robustification of Physics Parameters in Gas Networks (B06) (2014 - 2018)
TRR 154: Mathematical Modelling, Simulation and Optimisation Using the Example of Gas Networks (TRR 154)
July 1, 2014 - July 1, 2017
Involved external institutions
Germany (DE)How to cite
APA:
Liers, F., Martin, A., Merkert, M., Mertens, N., & Michaels, D. (2020). Towards the Solution of Mixed-Integer Nonlinear Optimization Problems using Simultaneous Convexification.
MLA:
Liers, Frauke, et al. Towards the Solution of Mixed-Integer Nonlinear Optimization Problems using Simultaneous Convexification. 2020.
BibTeX: Download