Face Dimensions of General-Purpose Cutting Planes for Mixed-Integer Linear Programs

Matthias Walter

doi:10.1007/978-3-030-73879-2_28

Face Dimensions of General-Purpose Cutting Planes for Mixed-Integer Linear Programs

Matthias Walter^*

^*Corresponding author for this work

Mathematics of Operations Research

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

9 Downloads (Pure)

Abstract

Cutting planes are a key ingredient to successfully solve mixed-integer linear programs. For specific problems, their strength is often theoretically assessed by showing that they are facet-defining for the corresponding mixed-integer hull. In this paper we experimentally investigate the dimensions of faces induced by general-purpose cutting planes generated by a state-of-the-art solver. Therefore, we relate the dimension of each cutting plane to its impact in a branch-and-bound algorithm.

Original language	English
Title of host publication	Integer Programming and Combinatorial Optimization
Subtitle of host publication	22nd International Conference, IPCO 2021, Atlanta, GA, USA, May 19–21, 2021, Proceedings
Editors	Mohit Singh, David P. Williamson
Publisher	Springer
Pages	399-412
Number of pages	14
ISBN (Electronic)	978-3-030-73879-2
ISBN (Print)	978-3-030-73878-5
DOIs	https://doi.org/10.1007/978-3-030-73879-2_28
Publication status	Published - 9 Jun 2021
Event	22nd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2021 - Virtual, Online Duration: 19 May 2021 → 21 May 2021 Conference number: 22

Publication series

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

Conference

Conference	22nd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2021
Abbreviated title	IPCO 2021
City	Virtual, Online
Period	19/05/21 → 21/05/21

Access to Document

10.1007/978-3-030-73879-2_28

ArticleFinal published version, 582 KBLicence: Taverne

Cite this

Walter, M. (2021). Face Dimensions of General-Purpose Cutting Planes for Mixed-Integer Linear Programs. In M. Singh, & D. P. Williamson (Eds.), Integer Programming and Combinatorial Optimization: 22nd International Conference, IPCO 2021, Atlanta, GA, USA, May 19–21, 2021, Proceedings (pp. 399-412). (Lecture Notes in Computer Science; Vol. 12707). Springer. https://doi.org/10.1007/978-3-030-73879-2_28

@inproceedings{5b8fda8c1efa4ab88a3bc6165c1ee7ee,

title = "Face Dimensions of General-Purpose Cutting Planes for Mixed-Integer Linear Programs",

abstract = "Cutting planes are a key ingredient to successfully solve mixed-integer linear programs. For specific problems, their strength is often theoretically assessed by showing that they are facet-defining for the corresponding mixed-integer hull. In this paper we experimentally investigate the dimensions of faces induced by general-purpose cutting planes generated by a state-of-the-art solver. Therefore, we relate the dimension of each cutting plane to its impact in a branch-and-bound algorithm.",

author = "Matthias Walter",

year = "2021",

month = jun,

day = "9",

doi = "10.1007/978-3-030-73879-2_28",

language = "English",

isbn = "978-3-030-73878-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "399--412",

editor = "Mohit Singh and Williamson, {David P.}",

booktitle = "Integer Programming and Combinatorial Optimization",

note = "22nd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2021, IPCO 2021 ; Conference date: 19-05-2021 Through 21-05-2021",

}

Walter, M 2021, Face Dimensions of General-Purpose Cutting Planes for Mixed-Integer Linear Programs. in M Singh & DP Williamson (eds), Integer Programming and Combinatorial Optimization: 22nd International Conference, IPCO 2021, Atlanta, GA, USA, May 19–21, 2021, Proceedings. Lecture Notes in Computer Science, vol. 12707, Springer, pp. 399-412, 22nd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2021, Virtual, Online, 19/05/21. https://doi.org/10.1007/978-3-030-73879-2_28

Face Dimensions of General-Purpose Cutting Planes for Mixed-Integer Linear Programs. / Walter, Matthias.

Integer Programming and Combinatorial Optimization: 22nd International Conference, IPCO 2021, Atlanta, GA, USA, May 19–21, 2021, Proceedings. ed. / Mohit Singh; David P. Williamson. Springer, 2021. p. 399-412 (Lecture Notes in Computer Science; Vol. 12707).

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

TY - GEN

T1 - Face Dimensions of General-Purpose Cutting Planes for Mixed-Integer Linear Programs

AU - Walter, Matthias

N1 - Conference code: 22

PY - 2021/6/9

Y1 - 2021/6/9

N2 - Cutting planes are a key ingredient to successfully solve mixed-integer linear programs. For specific problems, their strength is often theoretically assessed by showing that they are facet-defining for the corresponding mixed-integer hull. In this paper we experimentally investigate the dimensions of faces induced by general-purpose cutting planes generated by a state-of-the-art solver. Therefore, we relate the dimension of each cutting plane to its impact in a branch-and-bound algorithm.

AB - Cutting planes are a key ingredient to successfully solve mixed-integer linear programs. For specific problems, their strength is often theoretically assessed by showing that they are facet-defining for the corresponding mixed-integer hull. In this paper we experimentally investigate the dimensions of faces induced by general-purpose cutting planes generated by a state-of-the-art solver. Therefore, we relate the dimension of each cutting plane to its impact in a branch-and-bound algorithm.

UR - http://www.scopus.com/inward/record.url?scp=85106183804&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-73879-2_28

DO - 10.1007/978-3-030-73879-2_28

M3 - Conference contribution

AN - SCOPUS:85106183804

SN - 978-3-030-73878-5

T3 - Lecture Notes in Computer Science

SP - 399

EP - 412

BT - Integer Programming and Combinatorial Optimization

A2 - Singh, Mohit

A2 - Williamson, David P.

PB - Springer

T2 - 22nd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2021

Y2 - 19 May 2021 through 21 May 2021

ER -

Walter M. Face Dimensions of General-Purpose Cutting Planes for Mixed-Integer Linear Programs. In Singh M, Williamson DP, editors, Integer Programming and Combinatorial Optimization: 22nd International Conference, IPCO 2021, Atlanta, GA, USA, May 19–21, 2021, Proceedings. Springer. 2021. p. 399-412. (Lecture Notes in Computer Science). doi: 10.1007/978-3-030-73879-2_28

Face Dimensions of General-Purpose Cutting Planes for Mixed-Integer Linear Programs

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Face Dimensions of General-Purpose Cutting Planes for Mixed-Integer Linear Programs

Cite this