Determining Sharp Proximity Bounds for Low Row Rank and Δ-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 [Formula: see text] 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 [Formula: see text] (where we call the rank-m matrix A [Formula: see text]-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 [Formula: see text]-modular matrices up to unimodular transformation, we calculate sharp proximity bounds for small m and [Formula: see text] 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].