Computing Optimality Certificates for Convex Mixed-Integer Nonlinear Problems

Halbig K, Hümbs L, Rösel F, Schewe L, Weninger D (2024)

Publication Type: Journal article

Publication year: 2024

Journal

Informs Journal on Computing INFORMS (Institute for Operations Research and Management Sciences)

Book Volume: 36

Pages Range: 1579-1610

Journal Issue: 6

DOI: 10.1287/ijoc.2022.0099

Abstract

Every optimization problem has a corresponding verification problem that checks whether a given optimal solution is in fact optimal. In the literature, there are a lot of such ways to verify optimality for a given solution, for example, the branch-and-bound tree. To simplify this task, optimality certificates were introduced for convex mixed-integer nonlinear programs, and it was shown that the sizes of the certificates are bounded in terms of the number of integer variables. We introduce an algorithm to compute the certificates and conduct computational experiments. Through the experiments, we show that the optimality certificates can be surprisingly small.

Authors with CRIS profile

Katrin Halbig Economics - Discrete Optimization - Mathematics (EDOM) Lukas Hümbs Sonderforschungsbereich/Transregio 154 Mathematische Modellierung, Simulation und Optimierung am Beispiel von Gasnetzwerken Florian Rösel Professur für Optimization under Uncertainty & Data Analysis Dieter Weninger Economics - Discrete Optimization - Mathematics (EDOM)

Involved external institutions

Maxwell Institute for Mathematical Sciences

United Kingdom (GB)

How to cite

APA:

Halbig, K., Hümbs, L., Rösel, F., Schewe, L., & Weninger, D. (2024). Computing Optimality Certificates for Convex Mixed-Integer Nonlinear Problems. Informs Journal on Computing, 36(6), 1579-1610. https://doi.org/10.1287/ijoc.2022.0099

MLA:

Halbig, Katrin, et al. "Computing Optimality Certificates for Convex Mixed-Integer Nonlinear Problems." Informs Journal on Computing 36.6 (2024): 1579-1610.

BibTeX: Download