Muestra métricas de impacto externas asociadas a la publicación. Para mayor detalle:
| Indexado |
|
||||
| DOI | 10.1007/S10107-024-02092-1 | ||||
| Año | 2024 | ||||
| Tipo | artículo de investigación |
Citas Totales
Autores Afiliación Chile
Instituciones Chile
% Participación
Internacional
Autores
Afiliación Extranjera
Instituciones
Extranjeras
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.
| Ord. | Autor | Género | Institución - País |
|---|---|---|---|
| 1 | MUNOZ-ARIAS, GONZALO ALEJANDRO | Hombre |
Universidad de Chile - Chile
|
| 2 | Paat, Joseph | Hombre |
UNIV BRITISH COLUMBIA - Canadá
UBC Sauder School of Business - Canadá |
| 3 | Serrano, Felipe | Hombre |
COPT GmbH - Alemania
|
| Fuente |
|---|
| Fondo Nacional de Desarrollo Científico y Tecnológico |
| Natural Sciences and Engineering Research Council of Canada |
| Agencia Nacional de Investigación y Desarrollo |
| National Research and Development Agency of Chile |
| Agradecimiento |
|---|
| The authors would like to thank Roberto Cominetti for fruitful discussions; in particular, for discussions leading to Remark 1.3, for noticing the subtlety in Theorem 17.3 from [29] discussed in Remark 4.1, and for the example provided in the latter. The authors would also like to thank the anonymous reviewers for their insightful comments that greatly helped in improving the article. |
| J. Paat was supported by a Natural Sciences and Engineering Research Council of Canada Discovery Grant [RGPIN-2021-02475]. G. Mu\u00F1oz was supported by the National Research and Development Agency of Chile (ANID) through the Fondecyt Grant 1231522 and PIA/PUENTE AFB230002. |