Tightness of sensitivity and proximity bounds for integer linear programs

DOI10.1007/978-3-030-67731-2_25MaRDI QIDQ831833zbMATH OpenOpenAlexFDO

Authors Sebastian Berndt, Klaus Jansen, Alexandra Lassota

Publication date 24 March 2022

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

zbMATH Keywords

sensitivitylower boundsproximity

Mathematics Subject Classification ID

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

Abstract: We consider ILPs, where each variable corresponds to an integral point within a polytope $mathcalP$, i. e., ILPs of the form $min{c}^{op}xmidsu{m}_{pinmathcalPcapmathbb{Z}^d}{x}_{p}p=b,xinmathbb{Z}_{ge0}^{|mathcalPcapmathbb{Z}^d|}$. The distance between an optimal fractional solution and an optimal integral solution (called proximity) is an important measure. A classical result by Cook et al.~(Math. Program., 1986) shows that it is at most $Delt{a}^{Theta(d)}$ where $Delta$ is the largest coefficient in the constraint matrix. Another important measure studies the change in an optimal solution if the right-hand side $b$ is replaced by another right-hand side $b^{\prime }$. The distance between an optimal solution $x$ w.r.t.~$b$ and an optimal solution $x^{\prime }$ w.r.t.~$b^{\prime }$ (called sensitivity) is similarly bounded, i. e., $lVertb-b^{\prime }Ver{t}_{1}cdotDelt{a}^{Theta(d)}$, also shown by Cook et al. Even after more than thirty years, these bounds are essentially the best known bounds for these measures. While some lower bounds are known for these measures, they either only work for very small values of $Delta$, require negative entries in the constraint matrix, or have fractional right-hand sides. Hence, these lower bounds often do not correspond to instances from algorithmic problems. This work presents for each $Delta>0$ and each $d>0$ ILPs of the above type with non-negative constraint matrices such that their proximity and sensitivity is at least $Delt{a}^{Theta(d)}$. Furthermore, these instances are closely related to instances of the Bin Packing problem as they form a subset of columns of the configuration ILP. We thereby show that the results of Cook et al. are indeed tight, even for instances arising naturally from problems in combinatorial optimization.

Recommendations

• scientific article; zbMATH DE number 3904333
• Improving the Cook et al. proximity bound given integral valued constraints
• Some proximity and sensitivity results in quadratic integer programming
• Improving proximity bounds using sparsity
• Proximity in concave integer quadratic programming

Cites work

• scientific article; zbMATH DE number 6820261 (Why is no real title available?)
• scientific article; zbMATH DE number 7559087 (Why is no real title available?)
• scientific article; zbMATH DE number 227006 (Why is no real title available?)
• A Linear Programming Approach to the Cutting-Stock Problem
• A robust AFPTAS for online bin packing with polynomial migration
• A robust APTAS for the classical bin packing problem
• Approximation schemes for scheduling on parallel machines
• Convex separable optimization is not much harder than linear optimization
• Distances between optimal solutions of mixed-integer programs
• Distances to lattice points in knapsack polyhedra
• Factors and factorizations of graphs. Proof techniques in factor theory
• Friendly bin packing instances without integer round-up property
• Improving proximity bounds using sparsity
• Monotonizing linear programs with up to two nonzeroes per column
• Near-linear time algorithm for \(n\)-fold ILPs via color coding
• On deciding the non‐emptiness of 2SAT polytopes with respect to First Order Queries
• Online scheduling with bounded migration
• Polynomiality for bin packing with a constant number of item types
• Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma
• Robust approximation schemes for cube packing
• Robust polynomial-time approximation schemes for parallel machine scheduling with job arrivals and departures
• Scheduling jobs on identical and uniform processors revisited
• Sensitivity theorems in integer linear programming

Cited in

(14)

• On Proximity for k-Regular Mixed-Integer Linear Optimization
• scientific article; zbMATH DE number 6850361 (Why is no real title available?)
• Some proximity and sensitivity results in quadratic integer programming
• Nearness and bound relationships between an integer-programming problem and its relaxed linear-programming problem
• Improving proximity bounds using sparsity
• Proximity in concave integer quadratic programming
• Improving the Cook et al. proximity bound given integral valued constraints
• On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems
• Proximity bounds for random integer programs
• Proximity bounds for random integer programs
• Sensitivity theorems in integer linear programming
• Refined proximity and sensitivity results in linearly constrained convex separable integer programming
• scientific article; zbMATH DE number 3904333 (Why is no real title available?)
• Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma

This page was built for publication: Tightness of sensitivity and proximity bounds for integer linear programs

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