The distributions of functions related to parametric integer optimization

Oertel T, Paat J, Weismantel R (2020)

Publication Type: Journal article

Publication year: 2020

Journal

SIAM Journal on Applied Algebra and Geometry Society for Industrial and Applied Mathematics (SIAM)

Book Volume: 4

Pages Range: 422-440

Journal Issue: 3

DOI: 10.1137/19M1275954

Abstract

We consider the asymptotic distribution of the integer program (IP) sparsity function, which measures the minimal support of optimal IP solutions, and the IP to linear program (LP) distance function, which measures the distance between optimal IP and LP solutions. We create a framework for studying the asymptotic distributions of general functions related to integer optimization. There has been a significant amount of research focused on the extreme values that these functions can attain. However, less is known about their typical values. Each of these functions is defined for a fixed constraint matrix and objective vector while the right-hand sides are treated as input. We show that the typical values of these functions are smaller than the known worst case bounds by providing a spectrum of probability-like results that govern their overall asymptotic distributions.

Authors with CRIS profile

Timm Oertel Professur für Mathematische Analyse von Daten (Data Analytics)

Involved external institutions

Eidgenössische Technische Hochschule Zürich (ETHZ) / Swiss Federal Institute of Technology in Zurich CH Switzerland (CH) University of British Columbia CA Canada (CA)

How to cite

APA:

Oertel, T., Paat, J., & Weismantel, R. (2020). The distributions of functions related to parametric integer optimization. SIAM Journal on Applied Algebra and Geometry, 4(3), 422-440. https://dx.doi.org/10.1137/19M1275954

MLA:

Oertel, Timm, Joseph Paat, and Robert Weismantel. "The distributions of functions related to parametric integer optimization." SIAM Journal on Applied Algebra and Geometry 4.3 (2020): 422-440.

BibTeX: Download