Working with webworkers

[acco93]

First of all thank you very much for the solver! It is one of the few available in javascript & it is also very simple to use.

I'm trying to run the solver in a web worker but unfortunatly without success till now. Could you add a simple example of usage with web workers?

Thank you in advance and again for the solver;)

[bchevalier]

Hey,

I will investigate. In the meanwhile I am curious what type of application you are using the solver for that would require web workers. Is it a real time application? Also, do you use integer variables in your model?

[acco93]

It is just a simple university project where we investigate some methauristics to solve the generalized assignment problem. I'm using the solver to compute the linear relaxation needed in some algorithms (randomized rounding). It's not a real time application but I'd like to give the user the possibility to abort the computation >.< I use the solver with real variables but I use the values as probabilities to round them into integers (that is the randomized rounding principle). If you're interested here is a demo and the source code. N.B. I'm not a javascript expert so the code may be quite terrible ;)

[bchevalier]

Thanks for the link, that's an interesting project. I am familiar with simulated annealing, tabu search, grasp and local searches but I had never heard of randomized rounding before. That's interesting considering it could even be added as a feature to this solver.

Is it hard to model your problem to be compatible with randomized rounding? I imagine that the problem should be modelled in a way that guarantee that rounded variables do not make the problem infeasible. Do you have issues where the computation takes too long when using JSLP Solver? Does it always finish but you think it is sometimes too long? or do you think it is sometimes caught in an infinite loop?

By the way, your JavaScript look good, just one comment, it is usually recommended to write

variables[key]["cost"] = ...;

as follow:

variables[key].cost = ...;

(possibly because it used to be more optimized but might not matter much anymore)

[acco93]

Thanks for the advice!

Well, randomized rounding is just a probabilistic rounding of a continous solution when you need an integer one. It follows the principle "given a problem that needs an integer solution (and standard methods take too effort), compute the linear relaxation over some mathematical formulation (GAP has a very simple formulation but custom problems may have a difficult one) then round it probabilistically and this should be at least a sub-optimal solution". In general this approach doesn't produce a feasible solution so repeat the probabilistic rounding till a feasible one is produced.

When facing quite big problem instances such as this one Firefox kills my computer (probably swap overuse and then thrashing) while Chrome kills the page. Maybe in a pc with more RAM (Mine has 4 GB) this doesn't happen. Excluding extreme cases such as the previous one the solver always terminates in reasonable time.

[bchevalier]

I see, it is likely that this model is way too big for the solver in its current state. Your problem has in the order of magnitude of 1600 * 80 = 128000 variables but the solver can now handle only up to a few thousand variables at most due to numerical instability and unoptimized internal storage of the simplex tableau (we are in the process of making it more stable so that it can handle problems as large as this one but it won't happen very soon).

How long does it take before crashing? I was already thinking about adding a multithread mechanism to the solver because I want it to be usable by realtime applications. Would specifying a time-out value be enough? Or do you want to be able to terminate the process at any time?

[acco93]

It crashes almost immediatly (2-3 seconds). I'd like to run it in a web worker so as to stop it easily just stopping the worker. A timeout value could be useful in many applications but maybe would not solve the freezing problem, that is, you are forced to wait till the time is out. The possibility to terminate the process at any time is the general solution that could (once available) be easily modified to handle the timed processing also.

I tried to use the workers but the solver is composed by a lot of files and most of them require others in a quite intricate web xD so I get a lot of errors using the importScripts function that are probably related to the order in which I load the files. I couldn't get out of it so I opened an issue searching for help ;)

[JWally]

Question for you on this one:

At its core, are you just looking for a way to cancel the solver on demand?

[acco93]

Yes, basically that was the feature I was looking for.

To avoid the user interface freezing during long processing times I tried to run the solver not on the main thread but in background using web workers.

That was an old project, I might be missing some details. Anyway thanks for you interest!

[JWally]

Before I dig too deep into it; it looks like all the “required” made this thing untenable to put in a webworker. Is that right?

Naive question, if I wanted to do it; could I just take a browserified version of the library, put it in a webworker file; and go from there?

I tried looking into promises earlier today, but you’re still stuck with a mass of blocking loops...

For what it’s worth, there is a timeout on it now as well as a tolerance option that’s effective on problems where perfect is the enemy of good. To your point though; it would be nice to be able to kill it on demand; and not have it stop everything else...

On Thu, Oct 31, 2019 at 3:33 AM acco notifications@github.com wrote:

Yes, basically that was the feature I was looking for.

To avoid the user interface freezing during long processing times I tried to run the solver not on the main thread but in background using web workers.

That was an old project, I might be missing some details. Anyway thanks for you interest!

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/JWally/jsLPSolver/issues/54?email_source=notifications&email_token=AAS6F5ZOEBKVBCZS4DLYXZ3QRKJ6RA5CNFSM4C444542YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOECW5YUA#issuecomment-548265040, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAS6F56OZOHK5C6HAGPKIKDQRKJ6RANCNFSM4C44454Q .

[JWally]

This is actually kind of cool. Thanks for suggesting it!

So I bumped versions, and included the following lines:

https://github.com/JWally/jsLPSolver/blob/18942b7b670f9aeacf12f81397ad16a4692c1b5c/prod/solver.js#L3727-L3729

When solver is being initiated, it runs some (hacky) checks to see what environment its in. This looks to see if its in a webworker by seeing if "self" is globally defined. If it is, it attaches its self to self.

Through this, your webworker would look like this:

importScripts("/prod/solver.js");

console.log("SELF", self);

onmessage = function(d){
    var results = solver.Solve(d.data);
    postMessage(results);
};

and your html file would look like this:

            var w = new Worker("./worker.js");

            w.onmessage = function(d){console.log(d);}

            window.models = [];

            $(document).ready(function(){
                $.getJSON("/test/test-sanity/", function(problems){
                    for(var problem in problems){
                        $.getJSON("/test/test-sanity/" + problems[problem], function(model){
                            window.models.push(model);
                        });
                    }
                });

                // Run Our Expirement
                setTimeout(function(){
                    w.postMessage(window.models[1]);
                },3000)
            })

[acco93]

Thanks a lot!