Under what conditions does an Integer Programming problem run in polynomial time?

Question

Given $AX\leq B$ where $A\in\Bbb Z^{m\times n}$,$B\in\Bbb Z^m$ finding $X\in\Bbb Z^n$ where $m\geq n$ is the integer programming problem. If $A$ is totally unimodular then the problem is solvable in polynomial time ($(mn)^c$ arithmetic operations on $(mn)^c$ sized words suffices).

Supposing we have the promise that the number of feasible solutions is polynomial then under what conditions can the problem be solved in polynomial time using Kannan's and Barnivok's algorithm (other than total unimodularity)?

1. It may be possible that naturally defining IP with poly # solutions is in P unless somehow defined by Unique-SAT.

2. Is it possible that if perfect basis reduction for given problem is in P then Kannan's algorithm is in P?

3. Is there necessary and sufficient conditions on categories of inputs on which the algorithms run in poly time?

   It is unlikely that Kannan's algorithm or Barnivok's algorithm runs uniformly in $n^{O(n)}$ time for all inputs.

There is no evidence whatsoever that Kannan's or Barnivok's algorithm ever runs in poly time for any non-trivial class of inputs which is why the query. It seems unbelievable that there cannot be input families for which these terminate in poly time.

By non-trivial class of inputs I mean an exponential set of inputs.

https://cstheory.stackexchange.com/questions/37777/under-what-conditions-does-an-integer-programming-problem-run-in-polynomial-time

Answer 1

The way I think about Kannan's algorithm (or, for that matter, any of the several "Lenstra-type" algorithms which present similar bounds as the original Lenstra algo from 1983) is that it's designed with the extreme worst-case instances of integer programming (IP) in mind. The goal here is to get a small (i.e., polynomial) bound on the complexity of the general problem instance without any assumptions about any special structure of the input (matrix $A$, or even $B$).

Notice that IP with totally unimodular (TU) $A$ matrix is solvable in polynomial time not by Kannan's algorithm (or by any of the Lenstra-type algorithms), but by simply solving the IP as a linear program, which could be done in polynomial time, and we get integrality "for free" in that process. Other generalizations of TU matrices such as balanced matrices or total dual integrality (TDI) also guarantee integrality "for free" in a similar fashion as instances where $A$ is TU (some times with additional assumptions on $B$ also). Recently (STOC '17), Artmann, Weismantel, and Zenklusen gave a strongly polynomial algo for bimodular IPs, where $|\det(S)| \leq 2$ for all submatrices $S$ of $A$ (preprint might be available on ResearchGate). People have also considered the natural generalization of this problem where $|\det(S)| \leq \Delta$ for higher (but fixed) values of $\Delta$. The latest preprint by Gribanov provides an FTP algo for instances of IP where $A$ is "near square" (see the preprint for details). But again, all these families of algorithms somehow use the special problem structure, e.g., $|\det(S)| \leq \Delta$ (on a related note, we have studied (arXiv) a class of IP instances where $A$ is not TU, no fixed bound on $|\det(S)|$ is assumed, but still the LP relaxation of the IPs are guaranteed to have integer optimal solutions; but even here, the problems have a different kind of special structure).

In other words, the Lenstra-type algos (including Kannan's) are not designed to work better (or faster) on any specific subclass of IPs with special structure. As such, it's not surprising no such obvious instances have been identified as yet.