5

How to determine whether a convex polyhedron described by a set of linear inequalities contains at least a or no integer point in polynomial time, which is to say detecting the IP feasibility ?

Specially in binary case, it's sufficient to see if the polyhedron contains at least a binary(integer) vertex. Does the problem become easier in binary case ?

Brown
  • 173
  • 5
  • There cannot be a general polynomial time algorithm (unless P=NP), as we have ILPs who's feasibility problem is NP-complete. – Sune Oct 31 '22 at 18:45
  • Can you convert it to the form $Ax=b,x \geq 0$ where 0 is valid? Or do you have a specific set of points in mind to test? – Brannon Nov 01 '22 at 13:26

2 Answers2

1

Given that the feasible set of your problem is a nonempty finite set $S$ of integer points in Euclidean space, if you can find a linear representation of conv($S$) (the convex hull of $S$, which will be a polytope), you can use linear programming to find an extreme point of conv($S$). This can be done in polynomial time by using interior point methods. As the points of $S$ are all integers, the extreme points of conv($S$) are also all integers, so that finding an extreme point of conv($S$) is equivalent to finding a feasible (integer) solution to your problem. The caveat is that finding conv($S$) is generally hard.

Anselmo
  • 111
  • 3
  • The representation of conv(S) may not be polynomial to the number of inequalities defining S, nor the dimension of space, making solving the LP not polynomial. – xd y Nov 11 '22 at 05:13
1

As pointed out in a comment, the general answer would be "most likely no", because that would mean P is equal to NP.

Assume you have an oracle that, given a polyhedron $P = \{ x | A x \geq b\}$, can decide whether $P$ contains at least one integer point in polynomial time (polynomial in the size of $A$). This would allow you to answer the decision form of, say, graph coloring (which can embedded in a polynomial-size IP), in polynomial time. Namely, write down the IP, consider the polyhedron given by the continuous relaxation, add an objective constraint, and call your oracle. This would give you a polynomial-time oracle for graph coloring, which is an NP-complete problem. Therefore, graph coloring is in P and P = NP.

In some specific cases, the answer is trivially "yes". This includes:

  • Polyhedra that have a flow structure. Their extreme points are integer, so to prove there exists an integer point, all you need is to show it's not empty
  • Packing polyhedra, which are defined with constraints of the form $a^{T}x \leq b$ where all coefficients in $a, b$ are non-negative. The origin (zero) is trivially feasible, and it's integer.
  • Graph coloring without any restriction on the number of colors being used. Give a different color to each node.
mtanneau
  • 4,123
  • 11
  • 24
  • Hamiltonian Cycle (HC) is another example where we only need to find an integer feasible solution (when formulated as an I.P.) - nothing to maximise or minimise. – Shuxue Jiaoshou Nov 02 '22 at 05:55