Why can't Simplex Method solve big equations? Have I forgot something?

Question

I just wrote a Simplex Method in pure C-code and I have tested it. It works for the objective function:

$$\max: c^T x$$ With subject to: $$Ax \le b \\ x \ge 0$$

Here is an example:

#include <time.h>
#include "LinearAlgebra/declareFunctions.h"

int main() {

    clock_t start, end;
    float cpu_time_used;
    start = clock();

    double A[2*2] ={3,   3,
                   2,   4};

    double b[2] = {120,
                   150};

    double c[2] = {10,
                  12};
    double x[2];
    linprog(c, A, b, x, 2, 2);

    // Solution
    print(x, 2, 1);

    end = clock();
    cpu_time_used = ((float) (end - start)) / CLOCKS_PER_SEC;
    printf("\nTotal speed  was %f,", cpu_time_used);
    return 0;
}

Solution is:

5.000000000000000000 
35.000000000000000000

Where $x_1 = 5, x_2 = 35$

I tried to verify and it works! http://simplex.tode.cz/en/lv4usjgeuxy

My algorithm is built by listen to patrickJMT from Youtube. The solution is:

#include <time.h>
#include "LinearAlgebra/declareFunctions.h"

int main() {

    clock_t start, end;
    float cpu_time_used;
    start = clock();

    double A[2*3] ={2, 3, 2,
                    1, 1, 2};

    double b[2] = {1000,
                   800};

    double c[3] = {7,
                   8,
                  10};
    double x[3];
    linprog(c, A, b, x, 2, 3);

    // Solution
    print(x, 3, 1);

    end = clock();
    cpu_time_used = ((float) (end - start)) / CLOCKS_PER_SEC;
    printf("\nTotal speed  was %f,", cpu_time_used);
    return 0;
}

Solution is:

200.000000000000000000 
0.000000000000000000 
300.000000000000000000 

Where $x_1 = 200, x_2 = 0, x_3 = 300$

But this Simplex Method only works for "simple" or "small" system equations.

If I try a big $A$ matrix and long $b$ vector, then I need to use regularization.

$$\max : (A^TA + \alpha I)^Tb x$$ With S.t to: $$(A^TA + \alpha I)x \le A^Tb \\ x \ge 0$$

The problem here for me is that in my code, I have a do-while loop that quits if all the negative values in the bottom tableau is equal or above zero(0). But if the matrix $A$ is too big, then I need to increase $\alpha$ to make it solvable. If $\alpha$ is small, then the do-while loop will loops for ever and never stop.

Questions:

1. Is there another criteria to stop the algorithm?

2. Can I use like an $\epsilon$ in Simplex Method that make sure it will solve? I don't know who to explain, but I have seen lot's of algorithms that using a "small number" here and there because the world isn't perfect and neither the data.

3. Is Simplex Method only suitable for "small" and "easy" data? Is there another algorithm else to use that can handle large matrices?

Here is my library if you wonder.

Answer 1

Here is the solution. All I need to do is to compare with a AND and OR gate. Pure logical math!

From

for(int i = 1; i < row_a; i++){
            value1 = *(tableau + i*(column_a+row_a+2) + pivotColumIndex); // Value in pivot column
            value2 = *(tableau + i*(column_a+row_a+2) + (column_a+row_a+2-1)); // Value in the b vector
            value3 = value2/value1;
            if(value3 < smallest){
                smallest = value3;
                pivotRowIndex = i;
            }
        }

To:

for(int i = 1; i < row_a; i++){
            value1 = *(tableau + i*(column_a+row_a+2) + pivotColumIndex); // Value in pivot column
            value2 = *(tableau + i*(column_a+row_a+2) + (column_a+row_a+2-1)); // Value in the b vector
            value3 = value2/value1;
            if( (value3 > 0  && value3 < smallest ) || smallest < 0 ){
                smallest = value3;
                pivotRowIndex = i;
            }
        }