A characterization of maximal homogeneous-quadratic-free sets
Keywords: quadratic programming, cutting planes, S-free sets, Intersection cuts
Abstract
The intersection cut framework was introduced by Balas in 1971 as a method for generating cutting planes in integer optimization. In this framework, one uses a full-dimensional convex S-free set, where S is the feasible region of the integer program, to derive a cut separating S from a non-integral vertex of a linear relaxation of S. Among all S-free sets, it is the inclusion-wise maximal ones that yield the strongest cuts. Recently, this framework has been extended beyond the integer case in order to obtain cutting planes in non-linear settings. In this work, we consider the specific setting when S is defined by a homogeneous quadratic inequality. In this 'quadratic-free' setting, every function Gamma:D-m -> D-n whrere D(k )is the unit sphere in R-k generates a maximal quadratic free set, it is the case that every full-dimensional maximal quadratic free set is generated by some Gamma. Our main result shows that the corresponding quadratic-free set is full-dimensional and maximal if and only if Gamma is non-expansive and satisfies a technical condition. This result yields a broader class of maximal S-free sets than previously known. Our result stems from a new characterization of maximal S-free sets (for general S beyond the quadratic setting) based on sequences that 'expose' inequalities defining the S-free set.
Más información
Título según WOS: | A characterization of maximal homogeneous-quadratic-free sets |
Volumen: | 210 |
Número: | 1-2 |
Fecha de publicación: | 2025 |
Página de inicio: | 641 |
Página final: | 668 |
Idioma: | English |
DOI: |
10.1007/s10107-024-02092-1 |
Notas: | ISI |