Colección SciELO Chile

Departamento Gestión de Conocimiento, Monitoreo y Prospección
Consultas o comentarios: productividad@anid.cl
Búsqueda Publicación
Búsqueda por Tema Título, Abstract y Keywords



A characterization of maximal homogeneous-quadratic-free sets
Indexado
WoS WOS:001230120700001
Scopus SCOPUS_ID:85193978075
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


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.

Revista



Revista ISSN
Mathematical Programming 0025-5610

Métricas Externas



PlumX Altmetric Dimensions

Muestra métricas de impacto externas asociadas a la publicación. Para mayor detalle:

Disciplinas de Investigación



WOS
Computer Science, Software Engineering
Mathematics, Applied
Operations Research & Management Science
Scopus
Mathematics (All)
Software
SciELO
Sin Disciplinas

Muestra la distribución de disciplinas para esta publicación.

Publicaciones WoS (Ediciones: ISSHP, ISTP, AHCI, SSCI, SCI), Scopus, SciELO Chile.

Colaboración Institucional



Muestra la distribución de colaboración, tanto nacional como extranjera, generada en esta publicación.


Autores - Afiliación



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

Muestra la afiliación y género (detectado) para los co-autores de la publicación.

Financiamiento



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

Muestra la fuente de financiamiento declarada en la publicación.

Agradecimientos



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.

Muestra la fuente de financiamiento declarada en la publicación.