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

<p>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)?</p>

CC BY-SA 3.0
2017-03-16T19:49:17.880Z
There is a new paper to appear in STOC 2017 which gives a polynomial time algorithm when the matrix A is bimodular. That is, the subdeterminant values are at most 2. This is a generalization of totally unimodular case. I don't think it is based on using specifically Kannan and Barvinok's algorithm. I could be wrong.
Chandra Chekuri
CC BY-SA 3.0
2017-03-16T20:48:25.063Z
The promise that the number of solutions is polynomial is a very weak promise.  Indeed, even the promise that there will be either 0 or 1 solutions is still pretty weak.  A polynomial-time algorithm for (ILP with the promise that there are either 0 or 1 feasible solutions) would yield a polynomial-time algorithm for Unique-SAT, which would in turn (by Valiant and Vazirani) would yield a randomized algorithm with polynomial expected running time for SAT.  See also http://cstheory.stackexchange.com/q/25263/5038.
D.W.
CC BY-SA 3.0
2017-03-16T22:01:57.343Z
@ChandraChekuri yes Kannan's and I believe Barvinok's algorithm has nothing to do with Unimodularity. I just mentioned do not use unimodularity because I did not want the case of total unimodularity discussed in solutions. It is unlikely that Kannan's algorithm or Barnivok's algorithm runs uniformly in $n^{O(n)}$ time for all inputs. For which inputs do the algorithms run in poly time?
Turbo
CC BY-SA 3.0
2017-03-16T22:03:06.257Z
@D.W. That is why I said 'under which conditions'.
Turbo
CC BY-SA 3.0
2017-03-17T00:03:58.033Z
How about total dual integrality? Can you be more specific what qualifies as a "condition"?
Sasho Nikolov
CC BY-SA 3.0
2017-03-17T00:49:00.367Z
@SashoNikolov I think Kannan's algorithm does not use this since it is not a linear programming relaxation. 'Can you be more specific what qualifies as a "condition"?' I am exactly wondering this (whether Kannan's algorithm or Barnovok's algorithm has ever been used in a non-trivial poly time situation).
Turbo
CC BY-SA 3.0
2017-03-17T01:40:57.150Z
Ok so you want to know when these two specific algorithms run in polynomial time? Why? Can you provide references for Kannan's and Barvinok's algorithms? (I know Kannan's IP algorithm, and Barvinok's lattice point counting algorithm. Do you mean the adaptation of Barvinok's that solves the IP rather than the counting problem?) More importantly, can you provide a reference for the fact that Kannan's or Barvinok's algorithm runs in polynomial time when the constraint matrix is TU?
Sasho Nikolov
CC BY-SA 3.0
2017-03-17T02:21:42.120Z
@SashoNikolov if number of points is poly then will Barnivok's algorithm run definitely in poly time? It likely cannot. However it may be possible that naturally defining IP with poly # solutions is in P unless somehow defined by Unique-SAT (as DW says). Kannan's alg is  in https://www.crcpress.com/Lattice-Basis-Reduction-An-Introduction-to-the-LLL-Algorithm-and-Its-Applications/Bremner/p/book/9781439807026 (it expands details on Kannan's papers in the relevant chapters). Is it possible that if perfect basis reduction for give problem is in P then Kannan's alg is in P? Even this I don't see.
Turbo
CC BY-SA 3.0
2017-03-17T02:23:21.103Z
There is no evidence whatsoever that Kannan's or Barnivok's alg 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 itme.
Turbo
<polynomial-time><integer-programming>
Under what conditions does an Integer Programming problem run in polynomial time?
Turbo
# Under what conditions does an Integer Programming problem run in polynomial time?

(Asked by: username_0 on 2017-03-16)

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

**Tags:** polynomial-time, integer-programming

> **Comments:**
> **username_1**: There is a new paper to appear in STOC 2017 which gives a polynomial time algorithm when the matrix A is bimodular. That is, the subdeterminant values are at most 2. This is a generalization of totally unimodular case. I don't think it is based on using specifically Kannan and Barvinok's algorithm. I could be wrong.  
> **username_2**: The promise that the number of solutions is polynomial is a very weak promise.  Indeed, even the promise that there will be either 0 or 1 solutions is still pretty weak.  A polynomial-time algorithm for (ILP with the promise that there are either 0 or 1 feasible solutions) would yield a polynomial-time algorithm for Unique-SAT, which would in turn (by Valiant and Vazirani) would yield a randomized algorithm with polynomial expected running time for SAT.  See also http://cstheory.stackexchange.com/q/25263/5038.  
> **username_0**: @ChandraChekuri yes Kannan's and I believe Barvinok's algorithm has nothing to do with Unimodularity. I just mentioned do not use unimodularity because I did not want the case of total unimodularity discussed in solutions. It is unlikely that Kannan's algorithm or Barnivok's algorithm runs uniformly in $n^{O(n)}$ time for all inputs. For which inputs do the algorithms run in poly time?  
> **username_0**: @username_2 That is why I said 'under which conditions'.  
> **username_3**: How about total dual integrality? Can you be more specific what qualifies as a "condition"?  
> **username_0**: @SashoNikolov I think Kannan's algorithm does not use this since it is not a linear programming relaxation. 'Can you be more specific what qualifies as a "condition"?' I am exactly wondering this (whether Kannan's algorithm or Barnovok's algorithm has ever been used in a non-trivial poly time situation).  
> **username_3**: Ok so you want to know when these two specific algorithms run in polynomial time? Why? Can you provide references for Kannan's and Barvinok's algorithms? (I know Kannan's IP algorithm, and Barvinok's lattice point counting algorithm. Do you mean the adaptation of Barvinok's that solves the IP rather than the counting problem?) More importantly, can you provide a reference for the fact that Kannan's or Barvinok's algorithm runs in polynomial time when the constraint matrix is TU?  
> **username_0**: @SashoNikolov if number of points is poly then will Barnivok's algorithm run definitely in poly time? It likely cannot. However it may be possible that naturally defining IP with poly # solutions is in P unless somehow defined by Unique-SAT (as DW says). Kannan's alg is  in https://www.crcpress.com/Lattice-Basis-Reduction-An-Introduction-to-the-LLL-Algorithm-and-Its-Applications/Bremner/p/book/9781439807026 (it expands details on Kannan's papers in the relevant chapters). Is it possible that if perfect basis reduction for give problem is in P then Kannan's alg is in P? Even this I don't see.  
> **username_0**: There is no evidence whatsoever that Kannan's or Barnivok's alg 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 itme.  

---

## 0 answers

