The distributions of functions related to parametric integer optimization
From MaRDI portal
Abstract: We consider the asymptotic distribution of the IP sparsity function, which measures the minimal support of optimal IP solutions, and the IP to LP distance function, which measures the distance between optimal IP and LP solutions. We create a framework for studying the asymptotic distribution of general functions related to integer optimization. There has been a significant amount of research focused around 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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3987367 (Why is no real title available?)
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 6850361 (Why is no real title available?)
- scientific article; zbMATH DE number 1860211 (Why is no real title available?)
- A Polyhedral Frobenius Theorem with Applications to Integer Optimization
- A counterexample to an integer analogue of Carathéodory's theorem
- An integer analogue of Carathéodory's theorem
- Carathéodory bounds for integer cones
- Computing the integer programming gap
- Deterministic Approximation Algorithms for the Nearest Codeword Problem
- Distances between optimal solutions of mixed-integer programs
- Distances to lattice points in knapsack polyhedra
- Elementary Methods in Number Theory
- LLL-reduction for integer knapsacks
- Lattice invariant valuations on rational polytopes
- Lectures on Polytopes
- Normality and covering properties of affine semigroups
- Note on the coefficients of rational Ehrhart quasi-polynomials of Minkowski-sums
- ON THE RELATION BETWEEN INTEGER AND NONINTEGER SOLUTIONS TO LINEAR PROGRAMS
- On Proximity for k-Regular Mixed-Integer Linear Optimization
- On integer programming and convolution
- On the (co)girth of a connected matroid
- On the complexity of integer programming
- On the limit distribution of Frobenius numbers
- Optimizing sparsity over lattices and semigroups
- Parametric integer programming in fixed dimension
- Probabilistic Analysis of the Multidimensional Knapsack Problem
- Sensitivity theorems in integer linear programming
- Sparse Solutions of Linear Diophantine Equations
- Sparsity of integer solutions in the average case
- The Flatness Theorem for Nonsymmetric Convex Bodies via the Local Theory of Banach Spaces
- The Integrality Number of an Integer Program
- The b-hull of an integer program
- The intractability of computing the minimum distance of a code
- The support of integer optimal solutions
- The value function of a mixed integer program. II
- The value function of a mixed integer program: I
- The width and integer optimization on simplices with bounded minors of the constraint matrices
Cited in
(10)- The integrality number of an integer program
- Sparse representation of vectors in lattices and semigroups
- Sparsity and integrality gap transference bounds for integer programs
- The gap function: evaluating integer programming models over multiple right-hand sides
- Sparsity and proximity transference in integer programming
- Improving the Cook et al. proximity bound given integral valued constraints
- On -modular integer linear problems in the canonical form and equivalent problems
- Proximity bounds for random integer programs
- Proximity bounds for random integer programs
- scientific article; zbMATH DE number 3953664 (Why is no real title available?)
This page was built for publication: The distributions of functions related to parametric integer optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5125408)
