Learning Cuts via Enumeration Oracles

arXiv2305.12197MaRDI QIDQ6510195FDOQ6510195

Authors: Daniel Thuerck, Boro Sofranac, Marc E. Pfetsch, Sebastian Pokutta 

Abstract: Cutting-planes are one of the most important building blocks for solving large-scale integer programming (IP) problems to (near) optimality. The majority of cutting plane approaches rely on explicit rules to derive valid inequalities that can separate the target point from the feasible set. Local cuts, on the other hand, seek to directly derive the facets of the underlying polyhedron and use them as cutting planes. However, current approaches rely on solving Linear Programming (LP) problems in order to derive such a hyperplane. In this paper, we present a novel generic approach for learning the facets of the underlying polyhedron by accessing it implicitly via an enumeration oracle in a reduced dimension. This is achieved by embedding the oracle in a variant of the Frank-Wolfe algorithm which is capable of generating strong cutting planes, effectively turning the enumeration oracle into a separation oracle. We demonstrate the effectiveness of our approach with a case study targeting the multidimensional knapsack problem (MKP).

This page was built for publication: Learning Cuts via Enumeration Oracles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6510195)