Relaxation strength for multilinear optimization: McCormick strikes back

Emily Schutte; Matthias Walter

doi:10.48550/arXiv.2311.08570

Relaxation strength for multilinear optimization: McCormick strikes back

Emily Schutte
, Matthias Walter

Mathematics of Operations Research

Research output: Working paper › Preprint › Academic

86 Downloads (Pure)

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
Publisher	ArXiv.org
DOIs	https://doi.org/10.48550/arXiv.2311.08570
Publication status	Published - 14 Nov 2023

Keywords

math.OC
cs.DM
math.CO
90C57
F.2.2

Access to Document

10.48550/arXiv.2311.08570

2311.08570v1Final published version, 209 KB

Cite this

@techreport{13f5f42592be476ea37855b2fc1228e7,

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's result by showing that the intersection of the relaxations of such linearizations and the extended flower relaxation are equally strong.",

keywords = "math.OC, cs.DM, math.CO, 90C57, F.2.2",

author = "Emily Schutte and Matthias Walter",

note = "10 pages, 4 figures",

year = "2023",

month = nov,

day = "14",

doi = "10.48550/arXiv.2311.08570",

language = "English",

publisher = "ArXiv.org",

type = "WorkingPaper",

institution = "ArXiv.org",

}

TY - UNPB

T1 - Relaxation strength for multilinear optimization

T2 - McCormick strikes back

AU - Schutte, Emily

AU - Walter, Matthias

N1 - 10 pages, 4 figures

PY - 2023/11/14

Y1 - 2023/11/14

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 - math.OC

KW - cs.DM

KW - math.CO

KW - 90C57

KW - F.2.2

U2 - 10.48550/arXiv.2311.08570

DO - 10.48550/arXiv.2311.08570

M3 - Preprint

BT - Relaxation strength for multilinear optimization

PB - ArXiv.org

ER -

Relaxation strength for multilinear optimization: McCormick strikes back

Abstract

Keywords

Access to Document

Fingerprint

Cite this