0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In the worst case, simplex has exponential time complexity. So depending on your definition of "big," it could take a very long time to solve. $\endgroup$ – Math1000 Nov 26 at 1:23
  • $\begingroup$ @Math1000 is it a way to reduce that time? Set an iteration limit or an constant in a if-ststement? I can accept if the solution is not 100% accurate. $\endgroup$ – Daniel Mårtensson Nov 26 at 1:35
  • 1
    $\begingroup$ No offense, but the problem is probably somewhere in your implementation, not the simplex algorithm itself. I am no expert in C so I cannot debug your code, unfortunately. You may want to ask on Stack Overflow if there is any error in your code that would be causing it to take a long time to run. $\endgroup$ – Math1000 Nov 26 at 2:14
  • 1
    $\begingroup$ But how large is "large"? That will give a clue about whether or not it should be working. The simplex algorithm should be able to handle fairly large problems. $\endgroup$ – littleO Nov 26 at 8:33
  • 1
    $\begingroup$ @Math1000 ok. Thank you. I looked up blands rule and it seems that I have been implementing it without knowing that the rule did actually exsist $\endgroup$ – Daniel Mårtensson Nov 27 at 0:29
1
$\begingroup$

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