论文标题
最大均质二次无二次套件的表征
A characterization of maximal homogeneous-quadratic-free sets
论文作者
论文摘要
Balas在1971年引入了交叉切割框架，作为一种在整数优化中生成切割平面的方法。在此框架中，一个人使用全维凸$ S $ free set，其中$ s $是整数程序的可行区域，以从$ s $的线性放松的非综合顶点中得出一个切割的$ s $。在所有$ s $ free套装中，最大程度的最大削减是最大的。最近，该框架已扩展到整数案例之外，以便在非线性设置中获得切割平面。在这项工作中，我们考虑$ s $由均质二次不平等定义时的特定设置。在此“二次无”设置中，每个函数$γ：d^m \ to d^n $，其中$ d^k $是$ \ mathbb {r}^k $中的单位磁盘，生成了不含二次的无用集的表示。虽然并非每个$γ$都会产生一个最大二次免费套件，但每一个最大最大二次不含套件都是由一些$γ$生成的。我们的主要结果表明，当且仅当$γ$具有非企业并满足技术条件时，相应的无二次套件是全维和最大的。该结果比以前已知的最大$ s $ free套件更广泛。我们的结果源于基于定义$ s $ free集合的序列的最大$ s $ free集（对于二次设置的一般$ s $）的新表征。
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 $Γ: D^m \to D^n$, where $D^k$ is the unit disk in $\mathbb{R}^k$, generates a representation of a quadratic-free set. While not every $Γ$ generates a maximal quadratic free set, it is the case that every full-dimensional maximal quadratic free set is generated by some $Γ$. Our main result shows that the corresponding quadratic-free set is full-dimensional and maximal if and only if $Γ$ 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.
