Ensuring integral maximizer from integral linear program

Question

An integral linear program is one that has a maximizer that is integral. Sometimes it's possible to prove that a particular LP has this property, for example by proving that it's constraint matrix is totally unimodular.

Suppose that we have an integral LP, how can we then efficiently find an integral maximizer? After all, the optimum may be achieved by (exponentially) many different maximizers rather than just the integral ones.

---

^{Cross-posted from CS.SE where no answers have been posted after two weeks.}

Answer 1

Given an integral LP, you can use a LP algorithm to compute in polynomial time

• the optimal value of the LP,

• a vertex of the feasible region (polytope) of the LP where the optimal value is attained.

Thus, if you know that the polytope is integral (i.e., all the vertices are integral), then you can indeed compute in polynomial time an integral maximizer. In particular, this applies if the constraint matrix is totally unimodular.

However, as noted in the comments by Laakeri, it is in general NP-hard to compute an integral maximizer if you only know that one exists. This follows by reduction from the NP-complete problem of feasibility of ILP:

1. If you can compute integral maximizers of LPs that have them, you can also determine if a given LP has an integral maximizer:

   • Using an LP algorithm, compute the optimal value $v$.

   • Run the integral maximizer finder to compute a point $x$. (If the algorithm crashes, outruns its allotted time, etc., just fix $x$ as some garbage point.)

   • Check that $x$ is an integral point, it satisfies the inequalities of the LP, and it gives value $v$.

   If this checks out, then $x$ is indeed an integral maximizer of the LP. Conversely, if the LP has an integral maximizer, the algorithm finds it by assumption.

2. An LP has an integral feasible point iff the constant $0$ objective function has an integral maximizer.