0

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}$.

Sebastian Oberhoff
  • 1,229
  • 3
    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$. – orangeskid Apr 21 '18 at 05:32
  • " 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. – fleablood Apr 21 '18 at 05:57
  • 1
    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. – Sebastian Oberhoff Apr 21 '18 at 06:00
  • Multiplying an entire row by a scalar only changes $\bf A$ and $\bf b$, not $\bf x$ (or $\bf s$, which it includes). –  Apr 21 '18 at 11:23
  • @Rahul see the additions I've made. You do change $\mathbf{s}$ when multiplying a row by a scalar. – Sebastian Oberhoff Apr 21 '18 at 21:14
  • You edited the question, but did you see my answer at all? – LinAlg Apr 22 '18 at 01:22
  • I see the problem. You have to first convert to equality form ${\bf Ax}=\bf b$, ${\bf x}\ge\bf0$ before you start multiplying rows by $-1$. –  Apr 22 '18 at 03:27
  • @Rahul that does not resolve the problem, because that turns $s_2=-1$ into $-s_2=1$ (for the example in the question). – LinAlg Apr 23 '18 at 17:39
  • @LinAlg: No it doesn't. See my answer. –  Apr 23 '18 at 18:23

2 Answers2

1

$$\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?

  • 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$. – LinAlg Apr 23 '18 at 19:09
  • @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. –  Apr 24 '18 at 07:00
  • 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. – LinAlg Apr 24 '18 at 12:12
  • 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. –  Apr 25 '18 at 04:49
  • @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. – Sebastian Oberhoff Apr 27 '18 at 20:03
  • @Sebastian: I'm not sure how else to understand the sentence "we can assume that our linear program is of the form $\max_\mathbf{x}(\mathbf{c}^T\mathbf{x})$ subject to $\mathbf{Ax=b}$ and $\mathbf{x\geq0}$" in which no slack variables are mentioned. As I understood it, the slack variables are included in the $\mathbf{A'x'= b'}$ equation mentioned earlier, which is now treated as the new $\mathbf{Ax= b}$. But I don't have your textbook, so I could be wrong. –  Apr 28 '18 at 06:09
0

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.

LinAlg
  • 19,822