<p>Let RLP <span class="math-container">$\equiv$</span> (Linear relaxation of the Integer Program).</p>
<p>In general, Integer Programming is NP-hard. <span class="math-container">$~$</span>And often, an integer optimal solution will lie in the interior of the feasible space of the RLP.</p>
<p>But what if one of the extreme points of the RLP (that is, a vertex of the LP polytope) is an optimal solution to the I.P.?  Does this make the search for an integer optimal solution any easier?</p>

CC BY-SA 4.0
2022-12-10T17:31:03.243Z
No, not in general.  For example, consider the standard reduction of 3-SAT to ILP.  If the given 3-SAT formula is satisfiable, the LP will have an optimal (that is, feasible, as there is no objective) integer solution.  That doesn't mean it is easy to find.  (You may complain that this ILP has no objective, but it is easy to add an artificial one that makes no difference.)
Neal Young
CC BY-SA 4.0
2022-12-10T20:51:17.510Z
Neal, thanks.. For 0-1 Integer Programs such as Max Independent Set and Max Clique, optimal integer solns (in fact, ALL integer feasible solns) will be extreme points of the RLP.. I was wondering if for example, Simplex method pivots for the RLP can be "re-routed" thru these integer solns.. Otherwise, starting from an opt. soln to the RLP, an opt. integer soln should (hopefully) be within a "small" number of jumps (or simplex pivots).. Just thinking loud.
Shuxue Jiaoshou
CC BY-SA 4.0
2022-12-10T21:07:11.873Z
Doesn't seem likely, even if the integer solutions are *optimal* extreme points in the RLP.  Note that not only is finding integer solutions of this kind NP-hard, it is a long-studied topic, e.g. in operations research, where as far as I know nothing as simple as what you describe works for any significant class of LPs.
Neal Young
<integer-programming><polytope>
Integer Program where an integer optimal solution is an extreme point of the LP Relaxation
Shuxue Jiaoshou
# Integer Program where an integer optimal solution is an extreme point of the LP Relaxation

(Asked by: username_0 on 2022-12-10)

Let RLP $\equiv$ (Linear relaxation of the Integer Program).

In general, Integer Programming is NP-hard. $~$And often, an integer optimal solution will lie in the interior of the feasible space of the RLP.

But what if one of the extreme points of the RLP (that is, a vertex of the LP polytope) is an optimal solution to the I.P.? Does this make the search for an integer optimal solution any easier?

**Tags:** integer-programming, polytope
> **Comments:**
> **username_1**: No, not in general.  For example, consider the standard reduction of 3-SAT to ILP.  If the given 3-SAT formula is satisfiable, the LP will have an optimal (that is, feasible, as there is no objective) integer solution.  That doesn't mean it is easy to find.  (You may complain that this ILP has no objective, but it is easy to add an artificial one that makes no difference.)  
> **username_0**: Neal, thanks.. For 0-1 Integer Programs such as Max Independent Set and Max Clique, optimal integer solns (in fact, ALL integer feasible solns) will be extreme points of the RLP.. I was wondering if for example, Simplex method pivots for the RLP can be "re-routed" thru these integer solns.. Otherwise, starting from an opt. soln to the RLP, an opt. integer soln should (hopefully) be within a "small" number of jumps (or simplex pivots).. Just thinking loud.  
> **username_1**: Doesn't seem likely, even if the integer solutions are *optimal* extreme points in the RLP.  Note that not only is finding integer solutions of this kind NP-hard, it is a long-studied topic, e.g. in operations research, where as far as I know nothing as simple as what you describe works for any significant class of LPs.  

---

## 0 answers

