<p>Given an integral LP, you can use a LP algorithm to compute in polynomial time</p>
<ul>
<li><p>the optimal <em>value</em> of the LP,</p>
</li>
<li><p>a <em>vertex</em> of the feasible region (polytope) of the LP where the optimal value is attained.</p>
</li>
</ul>
<p>Thus, if you know that the <em>polytope</em> 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.</p>
<p>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:</p>
<ol>
<li><p>If you can compute integral maximizers of LPs that have them, you can also <em>determine</em> if a given LP has an integral maximizer:</p>
<ul>
<li><p>Using an LP algorithm, compute the optimal value <span class="math-container">$v$</span>.</p>
</li>
<li><p>Run the integral maximizer finder to compute a point <span class="math-container">$x$</span>. (If the algorithm crashes, outruns its allotted time, etc., just fix <span class="math-container">$x$</span> as some garbage point.)</p>
</li>
<li><p>Check that <span class="math-container">$x$</span> is an integral point, it satisfies the inequalities of the LP, and it gives value <span class="math-container">$v$</span>.</p>
</li>
</ul>
<p>If this checks out, then <span class="math-container">$x$</span> is indeed an integral maximizer of the LP. Conversely, if the LP has an integral maximizer, the algorithm finds it by assumption.</p>
</li>
<li><p>An LP has an integral feasible point iff the constant <span class="math-container">$0$</span> objective function has an integral maximizer.</p>
</li>
</ol>

CC BY-SA 4.0
2020-07-30T19:31:10.817Z
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.
orlp
CC BY-SA 4.0
2020-07-28T12:25:44.633Z
2020-07-30T19:55:51.323Z
2020-07-30T19:55:51.323Z
Emil Jeřábek
<p>An <a href="https://en.wikipedia.org/wiki/Linear_programming#Integral_linear_programs" rel="nofollow noreferrer">integral linear program</a> 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 <a href="https://en.wikipedia.org/wiki/Unimodular_matrix#Total_unimodularity" rel="nofollow noreferrer">totally unimodular</a>.</p>
<p>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.</p>
<hr />
<p><sup><a href="https://cs.stackexchange.com/questions/128250/ensuring-integral-result-from-integral-linear-program">Cross-posted</a> from CS.SE where no answers have been posted after two weeks.</sup></p>

CC BY-SA 4.0
2020-07-26T08:19:15.450Z
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.
Laakeri
CC BY-SA 4.0
2020-07-26T08:44:49.893Z
@Laakeri I'm assuming that we already have proven that the linear program is integral (_"suppose that we have an integral LP"_). My question is about finding that integer optimal solution. Your argument doesn't apply to this subclass of problems because the decider is trivial, it always returns yes.
orlp
CC BY-SA 4.0
2020-07-26T08:50:54.270Z
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.
Laakeri
CC BY-SA 4.0
2020-07-26T09:09:05.553Z
@Laakeri That is assuming a lot of things, perhaps there exist an efficient randomized algorithm that has a failure probability, and when not proven integral it's not distinguishable whether this failure happens due to non-integrality or just bad luck. Regardless, I'm also interested in solutions that only work for certain classes of integral LPs, such as those with totally unimodular constraint matrices.
orlp
CC BY-SA 4.0
2020-07-26T10:22:18.230Z
I think my argument is not assuming much. In your randomized algorithm example you could run the algorithm multiple times to make the probability of failure very small. If you are specifically interested in LPs with totally unimodular constraint matrices, then you should state that in the question.
Laakeri
CC BY-SA 4.0
2020-07-26T10:43:49.173Z
@Laakeri Also I'm not sure your argument still holds if we disallow a constant objective function, forcing it to be of the form $\max cx$ with an integral vector $c \neq \mathbf{0}$. Either way, the motivation of my question is that in many places I've seen logic of the sort "we've proven that the relaxation of an ILP $A$ is integral, therefore we can solve it in polynomial time using the relaxed LP", which I find somewhat suspect.
orlp
CC BY-SA 4.0
2020-07-26T13:10:13.733Z
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.
Emil Jeřábek
CC BY-SA 4.0
2020-07-26T13:17:49.367Z
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.
Emil Jeřábek
CC BY-SA 4.0
2020-07-26T20:40:47.583Z
Emil answered the main question of the op I presume. Another point is that if the problem is self-reducible you can find an integer maximizer or show that the LP is not integral.
Chandra Chekuri
CC BY-SA 4.0
2020-07-26T21:39:06.927Z
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. https://en.wikipedia.org/wiki/Linear_programming#Integral_linear_programs .  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.
Neal Young
CC BY-SA 4.0
2020-07-27T19:33:58.190Z
@NealYoung I did read that section from Wikipedia, and it also confused me. I quote: _"in an integral linear program, described in this section, variables are not constrained to be integers but rather one has proven somehow that the continuous problem always has an integral optimal value (assuming c is integral), and this optimal value may be found efficiently since all polynomial-size linear programs can be solved in polynomial time."_ I found this suspicious, which is part of the reason that lead to me asking this question. Re-reading I now realize it says optimal *value*, not *maximizer*.
orlp
CC BY-SA 4.0
2020-07-27T19:37:14.803Z
@EmilJeřábek If you post that as an answer I'll accept it.
orlp
CC BY-SA 4.0
2020-07-28T12:28:14.310Z
All right. ----
Emil Jeřábek
<linear-programming><integer-programming>
Ensuring integral maximizer from integral linear program
orlp
# Ensuring integral maximizer from integral linear program

(Asked by: username_0 on 2020-07-26)

An [integral linear program](https://en.wikipedia.org/wiki/Linear_programming#Integral_linear_programs) 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](https://en.wikipedia.org/wiki/Unimodular_matrix#Total_unimodularity).

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](https://cs.stackexchange.com/questions/128250/ensuring-integral-result-from-integral-linear-program) from CS.SE where no answers have been posted after two weeks.

**Tags:** linear-programming, integer-programming

> **Comments:**
> **username_1**: 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.  
> **username_0**: @username_1 I'm assuming that we already have proven that the linear program is integral (_"suppose that we have an integral LP"_). My question is about finding that integer optimal solution. Your argument doesn't apply to this subclass of problems because the decider is trivial, it always returns yes.  
> **username_1**: 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.  
> **username_0**: @username_1 That is assuming a lot of things, perhaps there exist an efficient randomized algorithm that has a failure probability, and when not proven integral it's not distinguishable whether this failure happens due to non-integrality or just bad luck. Regardless, I'm also interested in solutions that only work for certain classes of integral LPs, such as those with totally unimodular constraint matrices.  
> **username_1**: I think my argument is not assuming much. In your randomized algorithm example you could run the algorithm multiple times to make the probability of failure very small. If you are specifically interested in LPs with totally unimodular constraint matrices, then you should state that in the question.  
> **username_0**: @username_1 Also I'm not sure your argument still holds if we disallow a constant objective function, forcing it to be of the form $\max cx$ with an integral vector $c \neq \mathbf{0}$. Either way, the motivation of my question is that in many places I've seen logic of the sort "we've proven that the relaxation of an ILP $A$ is integral, therefore we can solve it in polynomial time using the relaxed LP", which I find somewhat suspect.  
> **username_2**: 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 username_1 wrote.  
> **username_2**: 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.  
> **username_3**: Emil answered the main question of the op I presume. Another point is that if the problem is self-reducible you can find an integer maximizer or show that the LP is not integral.  
> **username_4**: 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. https://en.wikipedia.org/wiki/Linear_programming#Integral_linear_programs .  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.  
> **username_0**: @NealYoung I did read that section from Wikipedia, and it also confused me. I quote: _"in an integral linear program, described in this section, variables are not constrained to be integers but rather one has proven somehow that the continuous problem always has an integral optimal value (assuming c is integral), and this optimal value may be found efficiently since all polynomial-size linear programs can be solved in polynomial time."_ I found this suspicious, which is part of the reason that lead to me asking this question. Re-reading I now realize it says optimal *value*, not *maximizer*.  
> **username_0**: @EmilJeřábek If you post that as an answer I'll accept it.  
> **username_2**: All right. ----  

---

## 1 answers

### Answer by username_2 on 2020-07-28. Score: 2 | Accepted answer

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 username_1, 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.

> **Comments:**
> **username_0**: 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.  

---

