Integer programming: Finding an integral solution in polynomial time

Question

I'm currently studying integer programming and I would like to confirm that the following understanding regarding how to find an integral solution in an integral polyhedron is correct.

Assume that an integer program is given where the corresponding polyhedron is integral (i. e. every face contains an integral solution). Most publications state that in order to find an integral, optimal solution to the IP we can simply solve the linear relaxation using a polynomial-time algorithm without specifying the algorithm any further. However, this does not seem to be sufficient in general, since a general LP algorithm might also return a fractional optimal solution, if there is more than one optimal solution (i. e. the optimal solution is not an extreme point of the polyhedron). The above procedure would work if we applied (e. g.) Karmakars algorithm, which returns a optimal basic solution (which is integral). I'm not sure about applying the ellipsoid method to the combination of the primal and the dual LP: I assume that this might return a fractional optimal solution.

Is my reasoning correct?

Thanks in advance!

Answer 1

Your interpretation of "integer polyhedron" (that every face contains an integer point) differs from what I believe is standard usage. My understanding (which matches the Wikipedia entry) is that for a polytope to be "integer", all vertices must be integer-valued. Under that definition, solving a linear program over the polytope is guaranteed to find an integer-feasible solution as long as the solution method (whether polynomial time or not) finds a basic feasible solution (vertex).