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

Matthias Walter

doi:10.48550/arXiv.2011.06076

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

Matthias Walter

Mathematics of Operations Research

Research output: Working paper

131 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
Publisher	ArXiv.org
Number of pages	12
DOIs	https://doi.org/10.48550/arXiv.2011.06076
Publication status	Published - 11 Nov 2020

Keywords

cs.DM
math.OC
90C11
G.2.0

Access to Document

10.48550/arXiv.2011.06076

2011.06076v1Final published version, 280 KB

1 Conference contribution

Face Dimensions of General-Purpose Cutting Planes for Mixed-Integer Linear Programs
Walter, M., 9 Jun 2021, Integer Programming and Combinatorial Optimization: 22nd International Conference, IPCO 2021, Atlanta, GA, USA, May 19–21, 2021, Proceedings. Singh, M. & Williamson, D. P. (eds.). Springer, p. 399-412 14 p. (Lecture Notes in Computer Science; vol. 12707).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Open Access
File
38 Downloads (Pure)

Cite this

@techreport{cbf6d588d5f04f13bdff5af7ac1c4e94,

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. ",

keywords = "cs.DM, math.OC, 90C11, G.2.0",

author = "Matthias Walter",

note = "12 pages, 32 figures, 1 table",

year = "2020",

month = nov,

day = "11",

doi = "10.48550/arXiv.2011.06076",

language = "English",

publisher = "ArXiv.org",

type = "WorkingPaper",

institution = "ArXiv.org",

}

TY - UNPB

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

AU - Walter, Matthias

N1 - 12 pages, 32 figures, 1 table

PY - 2020/11/11

Y1 - 2020/11/11

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.

KW - cs.DM

KW - math.OC

KW - 90C11

KW - G.2.0

U2 - 10.48550/arXiv.2011.06076

DO - 10.48550/arXiv.2011.06076

M3 - Working paper

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

PB - ArXiv.org

ER -

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

Abstract

Keywords

Access to Document

Fingerprint

Research output

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

Cite this