Speeding up calculations

[Guillaume84]

Hello!

This isn't so much an issue with your awesome algo. It's more a question of efficiency and speeding things up a little: how would I go about speeding up a very large calculation?

I have raised a question on SO and have also created a jsfiddle. I'd be very eager to hear what you think.

http://stackoverflow.com/questions/29413453/speed-up-simplex-algorithm http://jsfiddle.net/Guill84/qds73u0f/

I am relatively new to the world of mathematical optimisation -is there a way the problem I have defined can be broken down into smaller chunks or 'reframed' to speed up the calculations? Or is there a reason why it is slow? Perhaps it isn't slow at all given what I am trying to do.

Kind regards (and yours very humbly) G.

[JWally]

I cleaned out a piece of code that I think was holding it back. When I run your problem against it now on node.js, it clocks in at around 1.75s.

[Guillaume84]

Hello Justin!

Hope all is well. First of all -thank you so much for looking into this issue.

I am not sure what I am doing wrong but I updated the solver.js script and the problem seems to be taking double the time now. I am obviously doing something wrong, since you have achieved an impressive calculation time.

My jsfiddle: http://jsfiddle.net/qds73u0f/2/

Am I missing something here? Am very excited about your algo and would be eager to see if it could handle even meatier problems still! Be excited to compare it to other algorithms (e.g. What'sBest!) Am loving the simplicity of the array that gets fed into the algo and the straightforward javascript application.

Kind regards and thank you for your time, G.

[JWally]

Guillaume, Thank you for the kind words.

I don't have a formal background in math or comp. sci., but wanted to solve LP problems in the browser, so I created this. I just now added a hacky performance test to the grunt file:

grunt speed ​ Running in node.js on my old computer, it takes around 1,725ms to go through your problem on the first pass but 12,618ms to go through it on the second. If you want to help clean up some of the code and figure out what bottlenecks there are I would really appreciate it. I'll leave this issue open until I can at least figure out why its taking so long on the second run.

Just thinking as I type, but depending on your needs and how much bigger your problem sets get something like GLPK would probably be a better fit. Would would be nice though (probably a seperate project) is if you could feed a JSON problem into this and have it spit out a file that an industrial LP Solver could use.

On Fri, Apr 3, 2015 at 9:18 AM, Guillaume84 notifications@github.com wrote:

Hello Justin!

Hope all is well. First of all -thank you so much for looking into this issue.

I am not sure what I am doing wrong but I updated the solver.js script and the problem seems to be taking double the time now. I am obviously doing something wrong, since you have achieved an impressive calculation time.

My jsfiddle: http://jsfiddle.net/qds73u0f/2/

Am I missing something here? Am very excited about your algo and would be eager to see if it could handle even meatier problems still! Be excited to compare it to other algorithms (e.g. What'sBest!) Am loving the simplicity of the array that gets fed into the algo and the straightforward javascript application.

Kind regards and thank you for your time, G.

— Reply to this email directly or view it on GitHub https://github.com/JWally/jsLPSolver/issues/3#issuecomment-89301843.

[Guillaume84]

Hello Justin!

Apologies for the delay, have just returned from my easter break.

I have also looked into the code but am struggling to understand why it bottlenecks so badly. What performances do you get when you don't run the problem in Node?

Also, after your update from last week it looks like the problem now takes twice the amount of time to resolve?

Kind regards, G.

[JWally]

The biggest choke point looks like its coming from the big loop in the pivot function

        // for every row EXCEPT the target row,
        // set the value in the target column = 0 by
        // multiplying the value of all elements in the objective
        // row by ... yuck... just look below; better explanation later
        for (i = 0; i < length; i++) {
            if (i !== row) {
                pivot_row = tbl[i][col];
                for (j = 0; j < width; j++) {
                    tbl[i][j] += -pivot_row * tbl[row][j];
                }
            }
        }

On your model, every iteration of this takes about 55ms, and is called 135 times. I'm not sure how big of a hassle it would be, but I think there might be a speed enhancement if instead of using an array of arrays to store the tableau, I just went with a 1d Float32Array and treated it like a 2d array.

I was wrong earlier, when I run this in node on a 64 bit computer, it is indeed slow. On a 32bit, it takes about 1.7 seconds if you run your model cold; but ~13 seconds if you've run any other models before it.

[JWally]

Figured it out!

Changed the pivot function from above to this:

        // for every row EXCEPT the target row,
        // set the value in the target column = 0 by
        // multiplying the value of all elements in the objective
        // row by ... yuck... just look below; better explanation later
        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];
                    }
                }
            }
        }

On my 32 bit computer, this dropped the runtime on your problem from around 12 seconds to 0.6 seconds.