Maximal quadratic-free sets

• 成果类型: Article
• 署名作者: Munoz, Gonzalo; Serrano, Felipe
• 署名单位: Universidad de O'Higgins; Zuse Institute Berlin
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01738-8
• 发表日期: 2022
• 页码: 229-270
• 关键词: minimal valid inequalities; intersection cuts; integer variables; 2nd-order cone; optimization; disjunctions

摘要

The intersection cut paradigm is a powerful framework that facilitates the generation of valid linear inequalities, or cutting planes, for a potentially complex set S. The key ingredients in this construction are a simplicial conic relaxation of S and 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. However, maximality can be a challenging goal in general. In this work, we show how to construct maximal S-free sets when S is defined by 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.