The fixed--modular integer programming tractability conjecture

About 3 years old · traced to

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.

References

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).

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.