2
$\begingroup$

Consider the general linear programming problem

$min \sum_{j=1}^n c_jx_j$

s.t. $\sum_{j=1}^n a_{ij}x_j \leq b_i$, for $i=1,\dots , m$

$x_j \geq 0$ for $j=1,\dots , n$

And the corresponding extended formulation

$min \sum_{j=1}^n c_jx_j$

s.t. $\sum_{j=1}^n a_{ij}x_j + x_{n+i} = b_i$ for $i=1,\dots m$

$x_j\geq 0$ for $j=1,\dots,m+n$.

Show that both problems are equivalent. Hint: two problems $[A]$ and $[B]$ are equivelent if for each feasible solution of $[A]$ there is a corresponding feasible solution of $[B]$ with the same objective value and vice versa.


Being a feasible solution of $A$ means that all constraints of $A$ should be satisfied. However, I cannot seem to find a way to show that then all constraints of $B$ should also be satisfied. Can anyone please help me out?

$\endgroup$
  • $\begingroup$ @copper.hat My bad, I made a typo. I edited the post. $\endgroup$ – dreamer May 8 '13 at 18:59
1
$\begingroup$

In extended form the inequality constraints in first case can be written as $$a_{1,1}x_1+a_{1,2}x_2+...+a_{1,n}x_n\le b_1$$ $$a_{2,1}x_1+a_{2,2}x_2+...+a_{2,n}x_n\le b_2$$ $$...$$ $$a_{m,1}x_1+a_{m,2}x_2+...+a_{m,n}x_n\le b_m$$ Let's introduce some slack variables $x_{n+i}\ge 0$ into the inequality constraints such that $$a_{1,1}x_1+a_{1,2}x_2+...+a_{1,n}x_n+x_{n+1}= b_1$$ $$a_{2,1}x_1+a_{2,2}x_2+...+a_{2,n}x_n+x_{n+2}= b_2$$ $$...$$ $$a_{m,1}x_1+a_{m,2}x_2+...+a_{m,n}x_n+x_{n+m}= b_m$$ In short form $$\sum_{j=1}^{n} a_{i,j}x_j+x_{n+i}=b_i\quad for\,i=1,...,m$$ And the first case is transformed into the second one

------EDIT-------

We can rewrite the equality conditions in B such as $$\sum_{j=1}^{n} a_{i,j}x_j=b_i-x_{n+i}\quad for\,i=1,...,m$$ Since the question states that $x_j\ge 0$ for $j=1,...,m+n$ we can eliminate $x_j$ for $j> n$ by using inequality constraints without loss of generality such that $$\sum_{j=1}^{n} a_{i,j}x_j\le b_i\quad for\,i=1,...,m$$

$\endgroup$
  • $\begingroup$ Thank you for your help! I understand the concept of using slack variables, however, how does this show that every solution of the first problem is also a solution of the second problem with the same objective value? $\endgroup$ – dreamer May 8 '13 at 19:24
  • 1
    $\begingroup$ Because that makes both cases perfectly identical. If you want a more solid proof you can google "Karush-Kuhn-Tucker conditions". $\endgroup$ – AnilB May 8 '13 at 19:27
  • $\begingroup$ Ok :). By the way, isn't the proof in reverse order (so from B to A) exaclty identical (but then in the opposite direction) to this one? $\endgroup$ – dreamer May 8 '13 at 19:30
  • 1
    $\begingroup$ Check my edit for inverse transformation $\endgroup$ – AnilB May 8 '13 at 19:52
  • 1
    $\begingroup$ @cruise any time... $\endgroup$ – AnilB May 9 '13 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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