Zuse Institute Berlin (ZIB) の Dr. Felipe Serrano にご講演いただきます。
本勉強会は Zoom を用いてリアルタイム配信を行います。
Dr. Felipe Serrano (Zuse Institute Berlin)
Maximal Quadratic-Free Sets
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 inclusion-wise maximal, 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 talk, 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. We will also discuss some implementation details.
Copyright © 2013 NTT DATA Mathematical Systems Inc. All Rights Reserved.