Relaxation Strength for Multilinear Optimization: McCormick Strikes Back

Emily Schutte; Matthias Walter

doi:10.1007/978-3-031-59835-7_29

Relaxation Strength for Multilinear Optimization: McCormick Strikes Back

Emily Schutte, Matthias Walter^*

^*Corresponding author for this work

Mathematics of Operations Research

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

We consider linear relaxations for multilinear optimization problems. In a recent paper, Khajavirad proved that the extended flower relaxation is at least as strong as the relaxation of any recursive McCormick linearization (Operations Research Letters 51 (2023) 146–152). In this paper we extend the result to more general linearizations, and present a simpler proof. Moreover, we complement Khajavirad’s result by showing that the intersection of the relaxations of such linearizations and the extended flower relaxation are equally strong.

Original language	English
Title of host publication	Integer Programming and Combinatorial Optimization. Proceedings of 25th IPCO
Editors	Jens Vygen, Jaroslaw Byrka
Place of Publication	Wroclaw, Poland
Pages	393-404
Number of pages	12
ISBN (Electronic)	978-3-031-59835-7
DOIs	https://doi.org/10.1007/978-3-031-59835-7_29
Publication status	Published - 2024

Keywords

2024 OA procedure

Access to Document

10.1007/978-3-031-59835-7_29

Embargoed Document

Article
Final published version, 455 KB
Licence: Taverne
Embargo ends: 22/11/24

Cite this

@inproceedings{c4c55eb77ae54f2e9b0563e136439b85,

title = "Relaxation Strength for Multilinear Optimization: McCormick Strikes Back",

abstract = "We consider linear relaxations for multilinear optimization problems. In a recent paper, Khajavirad proved that the extended flower relaxation is at least as strong as the relaxation of any recursive McCormick linearization (Operations Research Letters 51 (2023) 146–152). In this paper we extend the result to more general linearizations, and present a simpler proof. Moreover, we complement Khajavirad{\textquoteright}s result by showing that the intersection of the relaxations of such linearizations and the extended flower relaxation are equally strong.",

keywords = "2024 OA procedure",

author = "Emily Schutte and Matthias Walter",

year = "2024",

doi = "10.1007/978-3-031-59835-7_29",

language = "English",

isbn = "978-3-031-59834-0",

pages = "393--404",

editor = "Jens Vygen and Jaroslaw Byrka",

booktitle = "Integer Programming and Combinatorial Optimization. Proceedings of 25th IPCO",

}

Relaxation Strength for Multilinear Optimization: McCormick Strikes Back. / Schutte, Emily; Walter, Matthias.
Integer Programming and Combinatorial Optimization. Proceedings of 25th IPCO. ed. / Jens Vygen; Jaroslaw Byrka. Wroclaw, Poland, 2024. p. 393-404.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Relaxation Strength for Multilinear Optimization

T2 - McCormick Strikes Back

AU - Schutte, Emily

AU - Walter, Matthias

PY - 2024

Y1 - 2024

N2 - We consider linear relaxations for multilinear optimization problems. In a recent paper, Khajavirad proved that the extended flower relaxation is at least as strong as the relaxation of any recursive McCormick linearization (Operations Research Letters 51 (2023) 146–152). In this paper we extend the result to more general linearizations, and present a simpler proof. Moreover, we complement Khajavirad’s result by showing that the intersection of the relaxations of such linearizations and the extended flower relaxation are equally strong.

AB - We consider linear relaxations for multilinear optimization problems. In a recent paper, Khajavirad proved that the extended flower relaxation is at least as strong as the relaxation of any recursive McCormick linearization (Operations Research Letters 51 (2023) 146–152). In this paper we extend the result to more general linearizations, and present a simpler proof. Moreover, we complement Khajavirad’s result by showing that the intersection of the relaxations of such linearizations and the extended flower relaxation are equally strong.

KW - 2024 OA procedure

U2 - 10.1007/978-3-031-59835-7_29

DO - 10.1007/978-3-031-59835-7_29

M3 - Conference contribution

SN - 978-3-031-59834-0

SP - 393

EP - 404

BT - Integer Programming and Combinatorial Optimization. Proceedings of 25th IPCO

A2 - Vygen, Jens

A2 - Byrka, Jaroslaw

CY - Wroclaw, Poland

ER -