<p>It is false. Consider the following (2 variable) LP:
<span class="math-container">\begin{align}
\max&amp;&amp; 3x+2y &amp; \\
&amp;&amp; 2x+y &amp;\leq 2 \\
&amp;&amp; 0 \leq x &amp;\leq 1 \\
&amp;&amp; 0 \leq y &amp;\leq 1
\end{align}</span></p>

CC BY-SA 4.0
2024-04-16T04:11:20.877Z
There is no optimum to the original LP that is integral right? The optimum objective value is 3.5 and no integral solution can achieve that. Sorry if I wasn't clear, I'll edit the question to be more precise.
gov
CC BY-SA 4.0
2024-04-16T05:39:14.280Z
So you're asking if there *is* an optimal integral solution and an optimal fractional solution, will the integral entries of the fractional solution agree with those of the integral solution? In that case, consider the same LP but change the objective function to $2x+y$
NaturalLogZ
CC BY-SA 4.0
2024-04-16T06:18:58.087Z
It's subtly different. I'm not talking about a specific optimal integral solution, rather just the existence of one. My question is whether fixing the LP variables that are integral will cause the resulting LP to not have *any* integral solutions. In your example, if you fix $y=1$ or $x=1$ from the fractional optimum, then there's still an integral solution for the resulting LP.
gov
CC BY-SA 4.0
2024-04-16T06:36:35.687Z
Ah okay, well then what if the first constraint is changed to be $2x+y=2$ (and the objective function is $2x+y$. Then the whole feasible region , which is a line segment, is optimal. One end of it is the integral point $(1,0)$ and the other is the fractional point $(1/2, 1)$. If you fix $y=1$ the resulting LP has no integral solutions.
NaturalLogZ
CC BY-SA 4.0
2024-04-16T03:13:32.460Z
2024-04-16T03:13:32.460Z
NaturalLogZ
<p>Suppose I have a linear program <span class="math-container">$LP1=\{\mbox{Maximize }c^\top x \mid x\in \mathcal{P}\}$</span> for some polytope <span class="math-container">$\mathcal{P}\subseteq [0,1]^n$</span>, which is known to have fractional extreme points. Suppose that we find some (possibly fractional) optimum <span class="math-container">$y^*$</span> to <span class="math-container">$LP1$</span>.</p>
<p>Let <span class="math-container">$I=\{i\mid y^*_i\in \{0,1\}\}$</span> be the set of indices for which <span class="math-container">$y^*$</span> has an integral value. If there exists an optimum for <span class="math-container">$LP1$</span> that is integral, will there also be an optimum for <span class="math-container">$LP2=\{\mbox{Maximize }c^\top x \mid x\in \mathcal{P}, \forall~i\in I, x_i=y^*_i  \}$</span> that is integral?</p>
<p>Put another way, what I am asking is the following. Suppose there is an optimum to some <span class="math-container">$LP1$</span> that is purely integral. If I solve <span class="math-container">$LP1$</span> to find a fractional solution <span class="math-container">$y^*$</span>, will there be an optimum to <span class="math-container">$LP1$</span> that is purely integral and also agrees with <span class="math-container">$y^*$</span> on the coordinates where <span class="math-container">$y^*$</span> is integral?</p>
<p>My feeling is that this is false, but I haven't been able to construct a counterexample for it. The motivation for my question is based on an iterative rounding process of an LP. If I keep solving and fixing integral variables, I was curious if some integral solution to the original LP remained feasible for the LP after fixing integral variables.</p>

<linear-programming><iterated-rounding>
Can you fix integral LP variables for a non-integral polytope without affecting the existence of integral optima?
gov
# Can you fix integral LP variables for a non-integral polytope without affecting the existence of integral optima?

(Asked by: username_0 on 2024-04-16)

Suppose I have a linear program $LP1=\{\mbox{Maximize }c^\top x \mid x\in \mathcal{P}\}$ for some polytope $\mathcal{P}\subseteq [0,1]^n$, which is known to have fractional extreme points. Suppose that we find some (possibly fractional) optimum $y^\*$ to $LP1$.

Let $I=\{i\mid y^\*\_i\in \{0,1\}\}$ be the set of indices for which $y^\*$ has an integral value. If there exists an optimum for $LP1$ that is integral, will there also be an optimum for $LP2=\{\mbox{Maximize }c^\top x \mid x\in \mathcal{P}, \forall~i\in I, x\_i=y^\*\_i \}$ that is integral?

Put another way, what I am asking is the following. Suppose there is an optimum to some $LP1$ that is purely integral. If I solve $LP1$ to find a fractional solution $y^\*$, will there be an optimum to $LP1$ that is purely integral and also agrees with $y^\*$ on the coordinates where $y^\*$ is integral?

My feeling is that this is false, but I haven't been able to construct a counterexample for it. The motivation for my question is based on an iterative rounding process of an LP. If I keep solving and fixing integral variables, I was curious if some integral solution to the original LP remained feasible for the LP after fixing integral variables.

**Tags:** linear-programming, iterated-rounding


---

## 1 answers

### Answer by username_1 on 2024-04-16. Score: 4 | Accepted answer

It is false. Consider the following (2 variable) LP:
\begin{align}
\max&& 3x+2y & \\
&& 2x+y &\leq 2 \\
&& 0 \leq x &\leq 1 \\
&& 0 \leq y &\leq 1
\end{align}

> **Comments:**
> **username_0**: There is no optimum to the original LP that is integral right? The optimum objective value is 3.5 and no integral solution can achieve that. Sorry if I wasn't clear, I'll edit the question to be more precise.  
> **username_1**: So you're asking if there *is* an optimal integral solution and an optimal fractional solution, will the integral entries of the fractional solution agree with those of the integral solution? In that case, consider the same LP but change the objective function to $2x+y$  
> **username_0**: It's subtly different. I'm not talking about a specific optimal integral solution, rather just the existence of one. My question is whether fixing the LP variables that are integral will cause the resulting LP to not have *any* integral solutions. In your example, if you fix $y=1$ or $x=1$ from the fractional optimum, then there's still an integral solution for the resulting LP.  
> **username_1**: Ah okay, well then what if the first constraint is changed to be $2x+y=2$ (and the objective function is $2x+y$. Then the whole feasible region , which is a line segment, is optimal. One end of it is the integral point $(1,0)$ and the other is the fractional point $(1/2, 1)$. If you fix $y=1$ the resulting LP has no integral solutions.  

---

