0

Suppose we have linear programming problem:

\begin{align*} \underset{x_1, x_2}{\operatorname{minimize}}\quad& c_1x_1+c_2x_2\\ \mbox{s.t.}\quad&a_{i1}x_1+a_{i2}x_2 \ge \beta_i\quad& (i = 1,\dots,n). \end{align*}

How do we get bounds on $x$ in its reformulation?

\begin{align*} \underset{x, y}{\operatorname{minimize}}\quad& y\\ \mbox{s.t.}\quad&y\ge a_ix+b_i\quad& (i\in I_1)\\ &y\le a_ix+b_i\quad& (i\in I_2)\\ &\color{red}{a\le x\le b}& \end{align*}

I think that here $y= c_1x_1+c_2x_2$ and $x = x_2$.

I would accept that $a$ and $b$ are natural bounds if there were such bounds in the original formulation. You can find these formulation in 2.1 here.

Yola
  • 1,665
  • 1
  • 18
  • 31

1 Answers1

1

In the second problem indeed $y=c_1 x_1 + c_2 x_2$ and $x=x_2$ (although you can also choose $x = x_1$ or any other linear combination of $x_1$ and $x_2$). Let us assume $c_1 \neq 0$, as otherwise the problem is trivial. Therefore, $x_1=(y-c_2x_2)/c_1$, and $$a_{i1}x_1 + a_{i2}x_2 \geq \beta_i$$ is equivalent to: $$a_{i1}(y-c_2x)/c_1 + a_{i2}x \geq \beta_i$$ If $a_{i1}=0$, you get either $x \geq \beta_i / a_{i2}$ or $x \leq \beta_i / a_{i2}$, leading to $a \leq x \leq b$. Otherwise you can rewrite the constraint to either $y \geq a_i x + b_i$ or $y \leq a_i x + b_i$.

LinAlg
  • 19,822