Simple Odd β -Cycle Inequalities for Binary Polynomial Optimization

Alberto Del Pia; Matthias Walter

doi:10.1007/978-3-031-06901-7_14

Simple Odd β -Cycle Inequalities for Binary Polynomial Optimization

Alberto Del Pia, Matthias Walter

Mathematics of Operations Research

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

6 Citations (Scopus)

86 Downloads (Pure)

Abstract

We consider the multilinear polytope which arises naturally in binary polynomial optimization. Del Pia and Di Gregorio introduced the class of odd β -cycle inequalities valid for this polytope, showed that these generally have Chvátal rank 2 with respect to the standard relaxation and that, together with flower inequalities, they yield a perfect formulation for cycle hypergraph instances. Moreover, they describe a separation algorithm in case the instance is a cycle hypergraph. We introduce a weaker version, called simple odd β -cycle inequalities, for which we establish a strongly polynomial-time separation algorithm for arbitrary instances. These inequalities still have Chvátal rank 2 in general and still suffice to describe the multilinear polytope for cycle hypergraphs.

Original language	English
Title of host publication	Integer Programming and Combinatorial Optimization. IPCO 2022
Subtitle of host publication	23rd International Conference, IPCO 2022, Eindhoven, The Netherlands, June 27–29, 2022, Proceedings
Editors	Karen Aardal, Laura Sanità
Place of Publication	Cham
Publisher	Springer
Pages	181–194
Number of pages	14
ISBN (Electronic)	978-3-031-06901-7
ISBN (Print)	978-3-031-06900-0
DOIs	https://doi.org/10.1007/978-3-031-06901-7_14
Publication status	Published - 2022
Event	23rd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2022 - Eindhoven, Netherlands Duration: 27 Jun 2022 → 29 Jun 2022 Conference number: 23

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	13265
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	23rd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2022
Abbreviated title	IPCO
Country/Territory	Netherlands
City	Eindhoven
Period	27/06/22 → 29/06/22

Keywords

Binary polynomial optimization
Cutting planes
Separation algorithm
22/2 OA procedure

Access to Document

10.1007/978-3-031-06901-7_14

DelPia2022simpleFinal published version, 396 KBLicence: Taverne

Cite this

Del Pia, A., & Walter, M. (2022). Simple Odd β -Cycle Inequalities for Binary Polynomial Optimization. In K. Aardal, & L. Sanità (Eds.), Integer Programming and Combinatorial Optimization. IPCO 2022: 23rd International Conference, IPCO 2022, Eindhoven, The Netherlands, June 27–29, 2022, Proceedings (pp. 181–194). (Lecture Notes in Computer Science; Vol. 13265). Springer. https://doi.org/10.1007/978-3-031-06901-7_14

Del Pia, Alberto ; Walter, Matthias. / Simple Odd β -Cycle Inequalities for Binary Polynomial Optimization. Integer Programming and Combinatorial Optimization. IPCO 2022: 23rd International Conference, IPCO 2022, Eindhoven, The Netherlands, June 27–29, 2022, Proceedings. editor / Karen Aardal ; Laura Sanità. Cham : Springer, 2022. pp. 181–194 (Lecture Notes in Computer Science).

@inproceedings{e07c079574494e5f88488825254856f9,

title = "Simple Odd β -Cycle Inequalities for Binary Polynomial Optimization",

abstract = "We consider the multilinear polytope which arises naturally in binary polynomial optimization. Del Pia and Di Gregorio introduced the class of odd β -cycle inequalities valid for this polytope, showed that these generally have Chv{\'a}tal rank 2 with respect to the standard relaxation and that, together with flower inequalities, they yield a perfect formulation for cycle hypergraph instances. Moreover, they describe a separation algorithm in case the instance is a cycle hypergraph. We introduce a weaker version, called simple odd β -cycle inequalities, for which we establish a strongly polynomial-time separation algorithm for arbitrary instances. These inequalities still have Chv{\'a}tal rank 2 in general and still suffice to describe the multilinear polytope for cycle hypergraphs.",

keywords = "Binary polynomial optimization, Cutting planes, Separation algorithm, 22/2 OA procedure",

author = "{Del Pia}, Alberto and Matthias Walter",

note = "Funding Information: A. Del Pia is partially funded by ONR grant N00014-19-1-2322. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the Office of Naval Research. M. Walter acknowledges funding support from the Dutch Research Council (NWO) on grant number OCENW.M20.151. Publisher Copyright: {\textcopyright} 2022, Springer Nature Switzerland AG.; 23rd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2022, IPCO ; Conference date: 27-06-2022 Through 29-06-2022",

year = "2022",

doi = "10.1007/978-3-031-06901-7_14",

language = "English",

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

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "181–194",

editor = "Karen Aardal and Laura Sanit{\`a}",

booktitle = "Integer Programming and Combinatorial Optimization. IPCO 2022",

address = "Germany",

}

Del Pia, A & Walter, M 2022, Simple Odd β -Cycle Inequalities for Binary Polynomial Optimization. in K Aardal & L Sanità (eds), Integer Programming and Combinatorial Optimization. IPCO 2022: 23rd International Conference, IPCO 2022, Eindhoven, The Netherlands, June 27–29, 2022, Proceedings. Lecture Notes in Computer Science, vol. 13265, Springer, Cham, pp. 181–194, 23rd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2022, Eindhoven, Netherlands, 27/06/22. https://doi.org/10.1007/978-3-031-06901-7_14

Simple Odd β -Cycle Inequalities for Binary Polynomial Optimization. / Del Pia, Alberto; Walter, Matthias.
Integer Programming and Combinatorial Optimization. IPCO 2022: 23rd International Conference, IPCO 2022, Eindhoven, The Netherlands, June 27–29, 2022, Proceedings. ed. / Karen Aardal; Laura Sanità. Cham: Springer, 2022. p. 181–194 (Lecture Notes in Computer Science; Vol. 13265).

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

TY - GEN

T1 - Simple Odd β -Cycle Inequalities for Binary Polynomial Optimization

AU - Del Pia, Alberto

AU - Walter, Matthias

N1 - Conference code: 23

PY - 2022

Y1 - 2022

N2 - We consider the multilinear polytope which arises naturally in binary polynomial optimization. Del Pia and Di Gregorio introduced the class of odd β -cycle inequalities valid for this polytope, showed that these generally have Chvátal rank 2 with respect to the standard relaxation and that, together with flower inequalities, they yield a perfect formulation for cycle hypergraph instances. Moreover, they describe a separation algorithm in case the instance is a cycle hypergraph. We introduce a weaker version, called simple odd β -cycle inequalities, for which we establish a strongly polynomial-time separation algorithm for arbitrary instances. These inequalities still have Chvátal rank 2 in general and still suffice to describe the multilinear polytope for cycle hypergraphs.

AB - We consider the multilinear polytope which arises naturally in binary polynomial optimization. Del Pia and Di Gregorio introduced the class of odd β -cycle inequalities valid for this polytope, showed that these generally have Chvátal rank 2 with respect to the standard relaxation and that, together with flower inequalities, they yield a perfect formulation for cycle hypergraph instances. Moreover, they describe a separation algorithm in case the instance is a cycle hypergraph. We introduce a weaker version, called simple odd β -cycle inequalities, for which we establish a strongly polynomial-time separation algorithm for arbitrary instances. These inequalities still have Chvátal rank 2 in general and still suffice to describe the multilinear polytope for cycle hypergraphs.

KW - Binary polynomial optimization

KW - Cutting planes

KW - Separation algorithm

KW - 22/2 OA procedure

U2 - 10.1007/978-3-031-06901-7_14

DO - 10.1007/978-3-031-06901-7_14

M3 - Conference contribution

SN - 978-3-031-06900-0

T3 - Lecture Notes in Computer Science

SP - 181

EP - 194

BT - Integer Programming and Combinatorial Optimization. IPCO 2022

A2 - Aardal, Karen

A2 - Sanità, Laura

PB - Springer

CY - Cham

T2 - 23rd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2022

Y2 - 27 June 2022 through 29 June 2022

ER -

Del Pia A, Walter M. Simple Odd β -Cycle Inequalities for Binary Polynomial Optimization. In Aardal K, Sanità L, editors, Integer Programming and Combinatorial Optimization. IPCO 2022: 23rd International Conference, IPCO 2022, Eindhoven, The Netherlands, June 27–29, 2022, Proceedings. Cham: Springer. 2022. p. 181–194. (Lecture Notes in Computer Science). doi: 10.1007/978-3-031-06901-7_14

Simple Odd β -Cycle Inequalities for Binary Polynomial Optimization

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this