Parametrizing an integer linear program by an integer

DOI10.1137/16M1102458MaRDI QIDQ3130449zbMATH OpenOpenAlexFDO

Authors Bobby Shen

Publication date 22 January 2018

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.01343

zbMATH Keywords

convex hullinteger programmingparametric integer linear programmingquasi-polynomial

Mathematics Subject Classification ID

Integer programming (90C10) Polynomial optimization (90C23) Sensitivity, stability, parametric optimization (90C31)

Abstract: We consider a family of integer linear programs in which the coefficients of the constraints and objective function are polynomials of an integer parameter $t.$ For $ell$ in $mathbb{Z}_{+},$ we define $f_{e}ll(t)$ to be the $el{l}^{extth}$ largest value of the objective function with multiplicity for the integer linear program at $t.$ We prove that for all $ell,$ $f_{e}ll$ is eventually quasi-polynomial; that is, there exists $d$ and polynomials $P_0,ldots,P_{d-1}$ such that for sufficiently large $t,$ $f_{e}ll(t)=P_{dpmodt}(t).$ Closely related to finding the $el{l}^{extth}$ largest value is describing the vertices of the convex hull of the feasible set. Calegari and Walker showed that if $R(t)$ is the convex hull of $mathbf{v}_1(t),ldots,mathbf{v}_k(t)$ where $mathbf{v}_i$ is a vector whose coordinates are in $mathbbQ(u)$ and of size $O(u),$ then the vertices of the convex hull of the set of lattice points in $R(t)$ has eventually quasi-polynomial structure. We prove this without the $O(u)$ assumption.

Recommendations

• Parametric integer programming in fixed dimension
• The integer hull of a convex rational polytope
• The integer hull of a convex rational polytope
• The parametric Frobenius problem
• La valeur optimale des programmes entiers. (The optimal value of integer programs)

Cites work

• Generalized Ehrhart polynomials
• scientific article; zbMATH DE number 3163858 (Why is no real title available?)
• scientific article; zbMATH DE number 1219584 (Why is no real title available?)
• Integer hulls of linear polyhedra and scl in families
• Polynomials Associated with Finite Gell-Complexes
• The unreasonable ubiquitousness of quasi-polynomials

Cited in

(4)

• Asymptotic behavior of integer programming and the stability of the Castelnuovo-Mumford regularity
• Parametric Presburger arithmetic: logic, combinatorics, and quasi-polynomial behavior
• A plethora of polynomials: a toolbox for counting problems
• A parametric version of LLL and some consequences: parametric shortest and closest vector problems

This page was built for publication: Parametrizing an integer linear program by an integer

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3130449)