Computing Optimality Certificates for Convex Mixed-Integer Nonlinear Problems

Katrin Halbig (), Lukas Hümbs (), Florian Rösel (), Lars Schewe () and Dieter Weninger ()
Additional contact information
Katrin Halbig: Department of Data Science, Friedrich-Alexander-Universität Erlangen-Nürnberg, 91058 Erlangen, Germany
Lukas Hümbs: Department of Data Science, Friedrich-Alexander-Universität Erlangen-Nürnberg, 91058 Erlangen, Germany
Florian Rösel: Department of Data Science, Friedrich-Alexander-Universität Erlangen-Nürnberg, 91058 Erlangen, Germany
Lars Schewe: School of Mathematics and Maxwell Institute for Mathematical Sciences, University of Edinburgh, Edinburgh EH9 3FD, United Kingdom
Dieter Weninger: Department of Data Science, Friedrich-Alexander-Universität Erlangen-Nürnberg, 91058 Erlangen, Germany

INFORMS Journal on Computing, 2024, vol. 36, issue 6, 1579-1610

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.

Keywords: programming - integer; nonlinear; programming - theory; programming - algorithms (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.0099 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:36:y:2024:i:6:p:1579-1610

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().