1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ In general this is NP-hard: Deciding if a linear program has a feasible integer solution is NP-hard, so you can just set a constant objective function so all feasible solutions are optimal. $\endgroup$ – Laakeri Jul 26 at 8:19
  • 2
    $\begingroup$ What happens if we have an unknown LP and suppose that it is integral, and then apply the algorithm to find an integral optimal solution? Now the algorithm either proves that the LP is indeed integral or results in some kind of error that we can notice. $\endgroup$ – Laakeri Jul 26 at 8:50
  • 2
    $\begingroup$ If the relaxation of an ILP is integral, you can find the value of the optimum in polynomial time. Perhaps this is the logic you've seen. Finding the maximizer is, indeed, NP-hard, as Laakeri wrote. $\endgroup$ – Emil Jeřábek Jul 26 at 13:10
  • 3
    $\begingroup$ Also, you can find in polynomial time a vertex of the feasible polytope where the optimum is attained. So, if you know that all vertices of the polytope are integral (which holds e.g. in the totally unimodular case), you can indeed find an integral maximizer in polynomial time. $\endgroup$ – Emil Jeřábek Jul 26 at 13:17
  • 2
    $\begingroup$ I think the OP has conflated terminology, namely, the difference between a particular LP (with objective function) being integral versus the polytope of that LP being integral. See e.g. en.wikipedia.org/wiki/… . The definition in the post seems correct for an LP, but for a polytope it is not. If the polytope is integral, by definition all of its vertices have to be integral, in which case, as @EmilJeřábek points out, you can find the optimum in polynomial time. $\endgroup$ – Neal Young Jul 26 at 21:39
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I would only like to add that we know the polytope is integral for totally unimodular LPs. Maybe you can edit that into your answer. If there are any other classes of LPs we know that have integral polytopes, I would love to know as well. $\endgroup$ – orlp Jul 30 at 19:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.