The polynomial-time solvability conjecture for totally -modular integer programs

Let AZm×nA\in\mathbb{Z}^{m\times n} be a totally Δ\Delta-modular matrix, meaning that every square submatrix of AA has determinant bounded by Δ\Delta in absolute value. For integer vectors b,wb,w and integer variable vector xx, consider the integer program

max{wTx:Axb, xZn}.\max\{w^Tx: Ax \leq b,\ x \in \mathbb{Z}^n\}.

Totally Δ\Delta-modular integer-program conjecture. For any constant Δ\Delta, this integer program can be solved in polynomial time when AA is totally Δ\Delta-modular.

The case Δ=1\Delta=1 is the totally unimodular case. Artmann, Weismantel, and Zenklusen answered the conjecture affirmatively for Δ=2\Delta=2, while the cases Δ3\Delta\geq 3 remain open.

Sources & referencesView supporting material

Primary source

Caleb McFarland, “Totally Δ-Modular Tree Decompositions of Graphic Matrices for Integer Programming”, arXiv:2602.01499 (2026).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.