Solver Freezes?

[natanielschling]

I'm building an app using ionic framework and my model has about 500 constraints and 5000 variables.

Here is the file model attached. model.txt

When I try to solve it, using solver.Solve(model), for exemple. The page freezes on my local environment. Is there any work around? Am I doing something wrong?

Thanks a lot :)

[bchevalier]

Hi,

Do you have the model under a json format that our solver can read so that we can test it as well? Our solver cannot parse the format you provide in the model.txt file. You can look at the README or at models located in test/problems for format samples.

Also, it looks like the model you are trying to solve has a significant number of binary variables. For now I am not sure the solver can handle that many variables without showing signs of numerical instability. However, we are currently in the process of updating the solver to handle such large problems but it might still take several weeks. How soon do you need this to work?

One more thing, it might be possible that your model can be simplified. If you do not mind explaining what your model corresponds to, we might be able to help you make it more solvable.

[natanielschling]

Hey Brice,

Thanks for the quick reply. Of course i don't mind to explain it. Let's go:

So, I've converted the generated model using JSON.stringify. model.json.zip

I think you can try to run it now. I do not have a static model in json, because my application uses a lot of custom parametrization and generates different constraints based on what the user chooses.

FYI: this model consists in to plan a optimal sequence of subscriptions in subjects of a University Graduation to get the degree early as possible. Here in Brazil, in private universities, we can choose how many subjects we are going to attend per semester, based on the timetables of each one and the personal available time of each student. In my prototype, the Production Engineer Graduation has 62 mandatory subjects. Each subject can have up to 16 different times to attend. In average, around 5 per subject. Also, i need to keep the University curriculum pre-requisites of each subject. And add some custom parametrization by the user. For example: user chooses to not have classes in Friday night.

So, each binary variable is a decision maker variable. For example: c01s0443 corresponds to: c01 = Subject 01 s04 = Semester 04 43 = Time of the class. In this case, Wednesday, at night.

If this one is equal to 1, the model is telling me that i need to attend the subject 01 at Wednesday night in the 4th semester of planned horizon.

I really don't know if i'm doing it in the best way. I'll be glad if you can give me some tips. This one is for my final paper in College :D. However, i need something funcional ASAP, since the deadline is June, 10th :(

[bchevalier]

Hi again,

Unfortunately, it looks like your project is ahead of the technology because our solver will probably not be ready to solve a timetabling problem of this size for several months. The 2nd bad news is that I do not know any other JavaScript solver able to solve this type of problem.

There are 2 solutions I suggest: 1 - Host a C++ or Java solver on a server and make the client app send the constraints to the hosted solver and then send back the solution to the client app. 2 - Implement a JavaScript meta-heuristic (genetic algorithm, tabu-search, etc...) to get an approximated solution to your problem. With time tabling problems, it is difficult to even find a feasible solution, so I am not sure how that would go.

We can keep your problem as a unit test for our solver and will let you know when we successfully solve it but I do not expect it to be before 4 or 5 months.

[natanielschling]

Well, keep this model as test, please. Meanwhile, I'll try to host a solver in a web server to make requests. Any tips for a head start?

Thanks a lot!

[bchevalier]

Sorry for the late reply, I have never done it myself, just know that it's doable. You can may be try Gurobi (http://www.gurobi.com/resources/seminars-and-videos/gurobi-compute-server), not sure if it works well but the description seems to indicate that it is a free to use solver (for academic purpose) that can run on the cloud.

[stuikomma]

Hi,

thanks for the great library. It solves (small instances of) my problem beautifully. However, with slighty larger instances I am also running into this issue (120 variables, 32 constraints). Simplex seems to get stuck at very small coefficients (around +-10e-20), which don't get skipped by this line if (coefficient !== 0) { in simplex.js:328.

Is there any update on this issue? Seems there has been some work going on around May/June 2016. How is https://github.com/JWally/jsLPSolver/issues/36. Would #55 be able to help in this case? Is there anything I could help with? Maybe cleaning up the PR #55?

[lvenerosy]

Hi,

Interesting, I thought I took care of all the zeros with a check in between a precision range.

Could you share your instance so that we can incorporate it in the test suite ?

[stuikomma]

Sure, here is one that works working.txt. This one takes a minute to solve in node.js, but within my application in Chrome I stopped it after 15min without a result onlyWorksInNode.txt.

I then made a small standalone version that only solves the model in the browser and voila, it also works. So there is probably some other library or so that interferes with the solver.

I'll keep you updated.

[stuikomma]

In my project I used webpack to bundle for the browser with source maps set to 'eval' (devtool: 'eval', docs). Turns out the choice of source maps significantly affects performance. I tried a few and they range from no effect (solving finishes in ~70s with 'none', 'inline-cheap-source-map' or 'inline-source-map') to decreased performance by >10x (using 'eval' or 'cheap-eval-source-map').

So I only have to change my source maps setting (and minimize the number of variables).

Thanks for your support :)

@lvenerosy You said that you 'took care of all the zeros with a check in between a precision range', does that mean this issue could be closed? The model posted by @natanielschling works for me.

[lvenerosy]

@stuikomma no I thought I did but I still have to check that part.

[chrispahm]

As a possible solution for solving large scale mixed integer problems, one could reformat the model into the GAMS format using this function. Then the model could be solved by using the NEOS server. The resulting GAMS listing file can be parsed by this function. I just finished a JS client for NEOS, which can then be used like the following:

// convert jsLPSolver model to GAMS
model = reformatGAMS(model)

// get NEOS solver Template, prepare the model, 
// submit, and wait for results
NEOS.getSolverTemplate('MILP', 'CPLEX', 'GAMS')
.then(template => {
  return NEOS.prepareJob(template, model, 'emailMandatoryForCPLEX@test.com')
})
.then(NEOS.submitJob)
.then(NEOS.getFinalResults)
.then(listing=> {
  const results = lstParse(listing)
// work with the results
})
.catch(err => {
  // catch errors
})

[JWally]

with the addition of "options.timeout" in the model, I'm gonna move to close this one unless anyone has any objections?

[JWally]

Also, @stuikomma , I ran your model for "only works in node" in the browser, and it appears to work; and drops all 0's!