Speed up simplex algorithm

Question

I am playing around with a great simplex algorithm I have found here: https://github.com/JWally/jsLPSolver/

I have created a jsfiddle where I have set up a model and I solve the problem using the algorithm above. http://jsfiddle.net/Guill84/qds73u0f/

The model is basically a long array of variables and constraints. You can think of it as trying to find the cheapest means of transportation of passengers between different hubs (countries), where each country has a minimum demand for passengers, a maximum supply of passengers, and each connection has a price. I don't care where passengers go, I just want to find the cheapest way to distribute them. To achieve this I use the following minimising objective:

model = {
        "optimize": "cost",
            "opType": "min",
            "constraints": { \\etc... 

I am happy with the model and the answer provided by the algorithm ... but the latter takes a very long time to run (>15 seconds...) Is there any possible way I can speed up the calculation?

Kind regards and thank you. G.

Answer 1

Figured it out. The most expensive piece of the code was the pivoting operation; which it turns out was doing a lot of work to update the matrix by adding 0. Doing a little logic up front to prevent this dropped my run-time down on node from ~12 seconds to ~0.5.

    for (i = 0; i < length; i++) {
        if (i !== row) {
            pivot_row = tbl[i][col];
            for (j = 0; j < width; j++) {


                // No point in doing math if you're just adding
                // Zero to the thing


                if (pivot_row !== 0 && tbl[row][j] !== 0) {
                    tbl[i][j] += -pivot_row * tbl[row][j];
                }
            }
        }
    }