Advancing mixed-integer programming using data-driven and deduction-based methods

Mixed-Integer Problems (MIPs) form one of the most general classes of optimization problems. As they are used to model many real-world scenarios, solving MIPs efficiently is crucial. Most solvers are based on the well-known Branch-and-Bound algorithm, which utilizes different subroutines to help find an optimal solution faster. In this dissertation, we focus on two of the most impactful components of MIP solving: Primal heuristics and cutting planes. First, we present two data-driven learning frameworks, offline and online, that aim to optimize the use of heuristics by learning from data describing their behavior. These approaches are able to improve performance of an state-of-the-art open-source MIP solver on a broad set of homogeneous and heterogeneous instances. In the second part of this thesis, we derive strong cutting planes to enforce quadratic constraints present in a MIP. By applying monoidal strengthening, we strengthen intersection cuts by exploiting integrality information. In addition, we show that, in our setting, unique lifting exists, implying that our strengthening procedure leads to the strongest cut coefficients. Finally, we present a general framework for cut generation to identify conditions under which a family of cutting planes yield a polyhedral closure. This allows us to show polyhedrality for a broad range of popular cuts more easily.

Author dc:creator

• Chmiela, Antonia

Advisor dc:contributor.advisor

• Pokutta, Sebastian

Licence dc:rights.uri

• https://creativecommons.org/licenses/by/4.0/

Language dc:language.iso

en

Identifier URI

https://doi.org/10.14279/depositonce-24040

OAI identifier oai:identifier

oai:depositonce.tu-berlin.de:11303/25218