1
$\begingroup$

I found these notes: https://www.math.ubc.ca/~loew/m340/rsm-notes.pdf on Google. I'm trying to implement this algorithm in C to help me learn about linear programming and programming in C. Right now I'm testing my code on the example given in the notes, but I'm running into an issue that so far seems to be a choice of starting indices (assuming I have not messed up).

The author picks the indices $\mathcal{B} = (4,5,6)$, $\mathcal{N} = (1,2,3)$ and goes on to do the method as described earlier in the notes. When I choose these indices, my program runs similarly.

However, since I won't always be there to judge, I wrote a snippet of code that finds the first $m$ linearly independent column vectors of matrix $A$ and records theses indices in $\mathcal{B}$. So in the example in the notes, my $\mathcal{B} = (1,2,3)$ and my $\mathcal{N} = (4,5,6)$.

This gives $B = \begin{bmatrix} 1 & 1 & 2 \\ 2 & 0 & 3 \\ 2 & 1 & 3 \end{bmatrix}$, $N = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$, $c_{\mathcal{B}}^T = \begin{bmatrix} 3 & 2 & 4 \\ \end{bmatrix}$, $c_{\mathcal{N}}^T = \begin{bmatrix} 0 & 0 & 0 \\ \end{bmatrix}$,

$x_{\mathcal{B}} = B^{-1}b = \begin{bmatrix} 4 \\ 2 \\ -1 \end{bmatrix}$,

$y^{T} = c_{\mathcal{B}}^{T}B^{-1} = \begin{bmatrix} -1 & -1 & 3 \\ \end{bmatrix}$,

$z_{\mathcal{N}}^{T} = y^{T}N - c_{\mathcal{N}}^{T} = \begin{bmatrix} -1 & -1 & 3 \\ \end{bmatrix}$,

Since the first entry of $z_{\mathcal{N}}^{T}$ is negative, we have that $E = 4$, $a^{(E)} = \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}$ and $d = B^{-1}a^{(E)} = \begin{bmatrix} -3 \\ 0 \\ 2 \end{bmatrix}$.

Now $x_{\mathcal{B}} -td$ never has zero for an entry for $t \geq 0$ so the algorithm should halt.

So I probably messed up somewhere, but I have been looking at this for several weeks and it's becoming unproductive to continue searching for a mistake that I might not have made. However, I just wanted to make sure that this algorithm doesn't depend on the starting choice of indices.

$\endgroup$
2
$\begingroup$

Good question. As noted on page 3 of those notes, “[y]ou need a feasible basis to get started” (emphasis mine). The indices you picked form a basis, but not a feasible basis. You can tell this because the corresponding basic solution $x_\mathcal{B}$ contains a negative entry. That is, it’s a basic solution, but not a basic feasible solution (BFS).

The trick they used in the example was easy because their $b$ vector has entirely non-negative entries. Typically an initial BFS is found using two-phase simplex.

$\endgroup$
  • $\begingroup$ Hey thanks for the reply! Yeah I was so confused, but glad to know all my work was not in vain. I'll google how to get a BFS to see how to do it and incorporate it into my work.. $\endgroup$ – Ceeerson Feb 22 at 0:08
  • $\begingroup$ Definitely. As I mentioned, that’s what two-phase simplex does $\endgroup$ – David M. Feb 22 at 0:08

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.