Maximal Quadratic-Free Sets

Das Schnittschneideparadigma ist ein mächtiges Rahmenwerk, das die Generierung gültiger linearer Ungleichheiten oder Schnittebenen für eine potenziell komplexe Gruppe S erleichtert. Die wichtigsten Bestandteile dieser Konstruktion sind eine vereinfachte konische Lockerung von S und eine S-freie Gruppe: eine konvexe Zone, deren Inneres sich nicht mit S überschneidet. Idealerweise wäre eine solche S-freie Gruppe maximale Inklusion, da sie eine tiefere Schneideebene erzeugen würde. Maximalität kann jedoch im Allgemeinen ein herausforderndes Ziel sein. In dieser Arbeit zeigen wir, wie man maximale S-freie Sätze konstruiert, wenn S als allgemeine quadratische Ungleichheit definiert wird. Unsere maximalen S-freien Sätze sind so, dass eine effiziente Trennung eines Scheitelpunktes in LP-basierten Ansätzen für quadratisch eingeschränkte Probleme garantiert ist. Unserer Kenntnis nach ist diese Arbeit die erste, die maximale quadratische Ungleichheit bietet.