Determining Sharp Proximity Bounds for Low Row Rank and $\mathrm{\Delta }$-Modularity

A question of great interest in integer programming is that of proximity bounding: How large can the distance be between an optimal vertex solution of the corresponding linear program relaxation and the closest integer optimal solution in the integer linear program? The proximity bound has many applications; for example, it can be used to bound the integrality gap and estimate nearby integer solutions in a dynamic programming framework. The maximum absolute subdeterminant of the coefficient matrix is known to be an important parameter for measuring the proximity bound. Here, we consider the integer program in the standard form $\max \{c^{\top }x: Ax=b,x\ge 0\}$ with a bounded feasible region, where the coefficient matrix A is of full row rank m and has a maximum order-m absolute subdeterminant of $\mathrm{\Delta }$ (where we call the rank-m matrix A $\mathrm{\Delta }$-modular). Using Wolsey’s b-hull results, we propose a method to determine the proximity bound for a fixed A and parametric b, c. Furthermore, by adapting an algorithm by Averkov and Schymura for classifying such rank-m $\mathrm{\Delta }$-modular matrices up to unimodular transformation, we calculate sharp proximity bounds for small m and $\mathrm{\Delta }$ using SageMath.

Funding: This research started during the 2023 University of California Davis Math Research Experiences for Undergraduates, supported by the National Science Foundation (NSF) [Grant DMS-1950928]. M. Köppe acknowledges partial support by the NSF [Grant DMS-2012764].