Maximal Quadratic-Free Sets.

Abstract: The intersection cut paradigm is a powerful framework that facilitates the generation of valid linear inequalities, or cutting planes, for a potentially complex feasible set S of an optimization problem. The key ingredient in this construction is an S-free set: a convex zone whose interior does not intersect S. Ideally, such S-free set would be maximal inclusion-wise, as it would generate a deeper cutting plane. In the case of integer programming, maximal lattice-free sets (i.e., when S corresponds to the integer lattice) have proven to be a powerful tool and have been carefully studied by the optimization community. In this work, we consider quadratically constrained optimization problems and show how to construct maximal S-free sets when S is defined as a general quadratic inequality. Our maximal S-free sets are such that efficient separation of a vertex in LP-based approaches to quadratically constrained problems is guaranteed. To the best of our knowledge, this work is the first to provide maximal quadratic-free sets.

Posted on Jul 27, 2020 in ACGO, Seminars