Advances on strictly -modular IPs

Area of Science:

• Optimization
• Computer Science
• Discrete Mathematics

Background:

• Integer programs (IPs) with bounded subdeterminants are a recent focus.
• A conjecture posits efficient solvability for k-modular IPs, where constraint matrix A has bounded k-minors.
• Progress often relies on solving strictly k-modular IPs, a restricted subclass.

Purpose of the Study:

• To extend efficient solvability of strictly k-modular IPs beyond the prime k case.
• To develop novel techniques not reliant on strong number-theoretic results specific to primes.
• To address the open conjecture for strictly k-modular IPs.

Main Methods:

• Development of new algorithmic techniques for integer programming.
• Focus on methods that do not depend on number-theoretic properties of prime numbers.
• Introduction of a randomized feasibility check for strictly k-modular IPs.

Main Results:

• First progress on strictly k-modular IPs beyond the prime k case.
• Demonstration of techniques applicable to non-prime k.
• A randomized algorithm for checking feasibility of strictly k-modular IPs when k is even, running in strongly polynomial time.

Conclusions:

• The study makes significant inroads into the challenging problem of k-modular integer programming.
• The developed techniques offer a path forward for non-prime cases, broadening applicability.
• The feasibility algorithm for even k represents a notable advancement in computational complexity for this class of problems.