The fixed--modular integer programming tractability conjecture

From papers

Let ΔZ>0\Delta \in \mathbb{Z}_{>0} be fixed. An integer program of the form (IP) has a constraint matrix BB that is Δ\Delta-modular if its full-rank minors have absolute value at most Δ\Delta and at least one has absolute value Δ\Delta.

Fixed-Δ\Delta tractability conjecture. There is a polynomial-time algorithm to solve any integer program of the form (IP) with a Δ\Delta-modular constraint matrix.

This conjecture extends the polynomial-time solvability of totally unimodular integer programs to every fixed bound on the maximal non-vanishing subdeterminants. Its status is not resolved in the supplied text.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Björn Kriepke, Gohar M. Kyureghyan and Matthias Schymura, “On the size of integer programs with bounded non-vanishing subdeterminants”, arXiv:2309.03772 (2023).

Solutions 0

No solutions have been posted yet.