Tightness of sensitivity and proximity bounds for integer linear programs

DOI10.1007/978-3-030-67731-2_25zbMATH Open1492.90089arXiv2010.09255OpenAlexW3126375186MaRDI QIDQ831833FDOQ831833

Authors: Sebastian Berndt, Klaus Jansen, Alexandra Lassota 

Publication date: 24 March 2022

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.

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

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

zbMATH Keywords

sensitivitylower boundsproximity

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (14)

• 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
• Title not available (Why is that?)
• Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma
• Refined proximity and sensitivity results in linearly constrained convex separable integer programming
• On Proximity for k-Regular Mixed-Integer Linear Optimization
• Title not available (Why is that?)

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)