Proximity guarantees of a lift-and-project approach for the cardinality-constrained Boolean quadric polytope

Walid Ben-Ameur

doi:10.1016/j.orl.2024.107166

Proximity guarantees of a lift-and-project approach for the cardinality-constrained Boolean quadric polytope

Walid Ben-Ameur

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

Résumé

We consider a lift-and-project approach for the cardinality-constrained Boolean quadric polytope. Some upper bounds for the distance between the polytope and its linear approximation are derived. Unsurprisingly, the distance converges to 0 when the number of variables increases sufficiently.

langue originale	Anglais
Numéro d'article	107166
journal	Operations Research Letters
Volume	57
Les DOIs	https://doi.org/10.1016/j.orl.2024.107166
état	Publié - 1 nov. 2024

Accès au document

10.1016/j.orl.2024.107166

Contient cette citation

@article{eb0eeac5155e49df8c794de939dd8be1,

title = "Proximity guarantees of a lift-and-project approach for the cardinality-constrained Boolean quadric polytope",

abstract = "We consider a lift-and-project approach for the cardinality-constrained Boolean quadric polytope. Some upper bounds for the distance between the polytope and its linear approximation are derived. Unsurprisingly, the distance converges to 0 when the number of variables increases sufficiently.",

keywords = "Boolean quadric polytope, Lift-and-project, Linear relaxations",

author = "Walid Ben-Ameur",

note = "Publisher Copyright: {\textcopyright} 2024 Elsevier B.V.",

year = "2024",

month = nov,

day = "1",

doi = "10.1016/j.orl.2024.107166",

language = "English",

volume = "57",

journal = "Operations Research Letters",

issn = "0167-6377",

}

TY - JOUR

T1 - Proximity guarantees of a lift-and-project approach for the cardinality-constrained Boolean quadric polytope

AU - Ben-Ameur, Walid

PY - 2024/11/1

Y1 - 2024/11/1

N2 - We consider a lift-and-project approach for the cardinality-constrained Boolean quadric polytope. Some upper bounds for the distance between the polytope and its linear approximation are derived. Unsurprisingly, the distance converges to 0 when the number of variables increases sufficiently.

AB - We consider a lift-and-project approach for the cardinality-constrained Boolean quadric polytope. Some upper bounds for the distance between the polytope and its linear approximation are derived. Unsurprisingly, the distance converges to 0 when the number of variables increases sufficiently.

KW - Boolean quadric polytope

KW - Lift-and-project

KW - Linear relaxations

U2 - 10.1016/j.orl.2024.107166

DO - 10.1016/j.orl.2024.107166

M3 - Article

AN - SCOPUS:85202302450

SN - 0167-6377

VL - 57

JO - Operations Research Letters

JF - Operations Research Letters

M1 - 107166

ER -

Proximity guarantees of a lift-and-project approach for the cardinality-constrained Boolean quadric polytope

Résumé

Accès au document

Empreinte digitale

Contient cette citation