0
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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}

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – gov
    Commented Apr 16 at 4:11
  • $\begingroup$ 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$ $\endgroup$ Commented Apr 16 at 5:39
  • $\begingroup$ 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. $\endgroup$
    – gov
    Commented Apr 16 at 6:18
  • 3
    $\begingroup$ 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. $\endgroup$ Commented Apr 16 at 6:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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