Valid Inequality Verification for MIP

305 Views Asked by At

I am asked to use the mixed integer rounding procedure to show that $$ x_2+x_4 \leq 20+4(y-2)$$ is a valid inequality for

X = {(x,y)$\in R_{+}^{4}* Z_{+}^{1}: x_1+x_2+x_3+x_4 \leq 10y , x_1\leq13,x_2\leq15,x_3\leq6,x_4\leq9$}

However, I don't know where to start giving the MIP rounding procedure depends mainly on integers, not real numbers.

I hope someone can help.

1

There are 1 best solutions below

2
On BEST ANSWER

The simple rounding inequality for $$\{(x,y) \in \mathbb R_+ \times \mathbb Z : y - x \le \beta\}$$ turns the inequality $y - x \le \beta$ into $$y - \frac{x}{1 - (\beta - \lfloor \beta \rfloor)} \le \lfloor \beta \rfloor \tag{$\star$}$$ The idea is that $(\star)$ is the splitting inequality we get from knowing that either $y \le \lfloor \beta \rfloor$ or $y \ge \lfloor \beta \rfloor+1$: it cuts off the non-integer point $(0,\beta)$ by a half-plane defined by the points $(0, \lfloor \beta \rfloor)$ and $(1 - (\beta - \lfloor \beta \rfloor),\lfloor \beta \rfloor+1)$.


When applying $(\star)$ to other problems, our first goal is to put our constraints on $y, x_2, x_4$ into a form similar to $y - x \le \beta$: we need a nonnegative real value to use as $x$.

We have two useful things we can say about $x_2 + x_4$: $$\begin{cases} x_2 + x_4 \le 10y \\ x_2 + x_4 \le 15 + 9 = 24 \end{cases}$$ So our nonnegative real variable can be $10y - x_2 - x_4$, and we can use that to write down the inequality $$10y - (10y - x_2 - x_4) \le 24 \implies y - (y - 0.1x_2 - 0.1x_4) \le 2.4$$ Applying $(\star)$ yields $$y - \frac{y - 0.1x_2 - 0.1x_4}{0.6} \le 2 \implies x_2 + x_4 \le 12 + 4y$$ as desired.