0
$\begingroup$

Problem 9.16 of The Nature of Computation states

Jumpstart for LP. How do we find an initial feasible solution for the simplex algorithm? By solving another linear program for which we know a feasible solution! As we outlined in Section 9.4.1, we can transform the set of inequalities $\mathbf{Ax\leq b}$ into a set of equalities $\mathbf{A'x'= b'}$ by adding "slack" variables $\mathbf{s\geq 0}$. Hence we can assume that our linear program is of the form $$ \max_\mathbf{x}(\mathbf{c}^T\mathbf{x})\qquad\text{subject to}\qquad \mathbf{Ax=b}\qquad\text{and}\qquad \mathbf{x\geq0}\,. $$ By adding more variables, construct yet another linear program that has a trivial feasible solution, and whose optimal solution is a feasible solution of this problem. Hint: if $\mathbf{b}\in\mathbb{R}^m$, you need $m$ additional variables. Without loss of generality you may assume that $\mathbf{b\geq 0}$.

I'm stuck understanding why one can assume that $\mathbf{b\geq 0}$. It seems that this assumption would lead straight to having $\mathbf{x=0}$ available as a trivial solution which is a little too easy.

There have been suggestions to just multiply every row in which $\mathbf{b}$ is negative by -1. I don't think it's that easy. Take the following example:

$$ \max_\mathbf{x}([1]\cdot\mathbf{x})\qquad\text{subject to}\qquad \begin{bmatrix} 1\\ -1 \end{bmatrix} \mathbf{x}\leq \begin{bmatrix} 2\\-1 \end{bmatrix} \qquad\text{and}\qquad \mathbf{x\geq 0} $$ It can easily be seen that this is maximized for $\mathbf{x}=[2]$. The corresponding problem with slack variables $\mathbf{s}$ has the same optimum and we must have $\mathbf{s}=[0\;1]^T$ to achieve equality. Now suppose we multiplied the second row by -1 to ensure $\mathbf{b\geq 0}$. Then $\mathbf{s}$ would have to become $[0\;-1]^T$ to still achieve equality, violating the constraint $\mathbf{s\geq 0}$.

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ Each linear constraint $\sum a_{ij} x_j = b_j$ is equivalent to $\sum (- a_{ij}) x_j= -b_j$. So you can find an equivalent problem with $b\ge 0$. $\endgroup$ – orangeskid Apr 21 '18 at 5:32
  • $\begingroup$ " It seems that this assumption would lead straight to having available as a trivial solution which is a little too easy." Well, there's nothing wrong with having the trivial solution being easy. You still have to find the other solutions. not making the assumption also leads to having x=0 as well. $\endgroup$ – fleablood Apr 21 '18 at 5:57
  • 1
    $\begingroup$ I don't see how you can multiply a row through with -1 and still guarantee that there's some $\mathbf{s\geq 0}$ that makes the whole thing work out. $\endgroup$ – Sebastian Oberhoff Apr 21 '18 at 6:00
  • $\begingroup$ Multiplying an entire row by a scalar only changes $\bf A$ and $\bf b$, not $\bf x$ (or $\bf s$, which it includes). $\endgroup$ – Rahul Apr 21 '18 at 11:23
  • $\begingroup$ @Rahul see the additions I've made. You do change $\mathbf{s}$ when multiplying a row by a scalar. $\endgroup$ – Sebastian Oberhoff Apr 21 '18 at 21:14
1
$\begingroup$

$$\max\, [1]^T[x] \quad \text{s.t.} \quad \begin{bmatrix}1\\-1\end{bmatrix}[x]\le\begin{bmatrix}2\\-1\end{bmatrix},\, [x]\ge 0$$

Add slack variables:

$$\max\, \begin{bmatrix}1\\0\\0\end{bmatrix}^T\begin{bmatrix}x\\s_1\\s_2\end{bmatrix} \quad \text{s.t.} \quad \begin{bmatrix}1&1&0\\-1&0&1\end{bmatrix}\begin{bmatrix}x\\s_1\\s_2\end{bmatrix}=\begin{bmatrix}2\\-1\end{bmatrix},\, \begin{bmatrix}x\\s_1\\s_2\end{bmatrix}\ge 0$$

Negate rows as necessary:

$$\max\, \begin{bmatrix}1\\0\\0\end{bmatrix}^T\begin{bmatrix}x\\s_1\\s_2\end{bmatrix} \quad \text{s.t.} \quad \begin{bmatrix}1&1&0\\1&0&-1\end{bmatrix}\begin{bmatrix}x\\s_1\\s_2\end{bmatrix}=\begin{bmatrix}2\\1\end{bmatrix},\, \begin{bmatrix}x\\s_1\\s_2\end{bmatrix}\ge 0$$

The optimum is at $x=2,s_1=0,s_2=1$. What's the problem?

|cite|improve this answer
$\endgroup$
  • $\begingroup$ The problem is finding the initial basis. Typically you start with $(s_1,s_2)$ as the basis, but this leads to $s_2 = -1$. $\endgroup$ – LinAlg Apr 23 '18 at 19:09
  • $\begingroup$ @LinAlg: I don't see how that's relevant. I am answering the OP's problem stated in the question, i.e. how you can transform any set of inequalities $Ax\le b,x\ge0$ into the constraints $A'x'=b',x'\ge0$ with $b'\ge0$. There is no basis involved here. That may show up later, when you try to "construct yet another linear program that has a trivial feasible solution ... by adding more variables". But that is not what the OP is asking about. $\endgroup$ – Rahul Apr 24 '18 at 7:00
  • $\begingroup$ The yellow block in the question starts with "How do we find an initial feasible solution for the simplex algorithm?" That's exactly what the two phase method is about. You do not use $b \geq 0$ in your solution method. $\endgroup$ – LinAlg Apr 24 '18 at 12:12
  • $\begingroup$ As I understand it, the yellow block is the context for the question. The OP's actual question is "I'm stuck understanding why one can assume that $b≥0$" and "There have been suggestions to just multiply every row in which $b$ is negative by $-1$. I don't think it's that easy", which is what I'm answering. But maybe we'll have to agree to disagree. $\endgroup$ – Rahul Apr 25 '18 at 4:49
  • $\begingroup$ @Rahul I'm quite surprised by how you added slack variables here. Both in the book I'm reading and on the Wikipedia page for slack variables they are added by turning $\mathbf{Ax\leq b}$ into $\mathbf{Ax+s=b}$. You did it instead by extending $\mathbf{A}$ and $\mathbf{x}$. I'm somewhat skeptical that this is what the authors intended, but I guess one can solve the exercise this way regardless. $\endgroup$ – Sebastian Oberhoff Apr 27 '18 at 20:03
0
$\begingroup$

You text you quote suggests to introduce artificial variables (after multiplying rows with -1 to if needed) and to change the system to $Ax+y=b$. The first steps in the simplex method aim at getting y to 0 by using the big-M method or the two phase method. See, e.g., this document for an explanation of the two phase method.

|cite|improve this answer
$\endgroup$

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.