Termination Tolerance Option

[chrispahm]

Most of the times the solution to a MIP problem does not have to be the absolute best possible solution, but rather a solution relatively close to the relaxed one. Modelling systems like GAMS or Gurobi therefore introduce a termination tolerance, where the solver will stop the solution process when the proportional difference between the solution found and the best theoretical objective function is guaranteed to be smaller than the given termination tolerance. I tried to add this option to the jsLPSolver, which can be used by passing the option „optcr“ as follows:

results = solver.Solve(model, 0.5);

This generally reduces the solve time for large scale MIPs significantly. The default value of Optcr is set to 0.1.

[bchevalier]

Thanks for the PR, that's a nice addition! Did you try on any particular model?

What would be nice:

• May be write the name optcr in full words (not sure what it means now, optimality criteria? also, in this project, variables are usually full words. May be tolerance is a better name? what do GAMS and Gurobi use?)
• Possibility to specify this optcr variable in json models.
• Add a json model to the test suite to demonstrate this feature
• Right now you are submitting a PR that only contains the build solver.js, meaning that if we build it again, your changes would be gone. Can you make sure to submit the changes in the src files? (any change should be done in the files located in src, the build src/solver.js is generated from all the other files in the folder using the grunt command I think after doing an npm install)

If that's too much work, we can actually make a PR with changes that would implement the functionality you are suggesting.

[chrispahm]

Thanks for the replies! To be honest, I never questioned the name optcr, even on the GAMS homepage it is not further explained. So I think calling it tolerance make a lot of sense. When solving the attached model, I found that the solver would not come up with a result within a reasonable time. When checking what parts took especially long, it looked like the sheer amount of branches is making the branch & cut loop take exceptionally long. If you run the model with a tolerance level of 0.2, it will solve in less than a second. You can also notice the change in the evaluation value if you increase the value further. I also tried solving the model mentioned in the following issue, however it turned out to be infeasible.

I will try to work in your suggestions over the weekend or the course of the next week.

LargeFarmMIP.json.zip

[bchevalier]

Thanks for the GAMS parser!

Actually, I think the reason why the model you linked (in this issue) is not feasible is simply that the solver is not able to tackle problems that are too big without experiencing numerical instability (rounding error propagation). We are currently working on solving that issue.

Also, I think that the tolerance should be updated at every iteration of the branch and cut to consider the new best possible evaluation. In the current state, I think your heuristic works well for small instances, but not for big ones where the evaluation of the relaxed solution can be less than 20% (if your tolerance is 20%) smaller than the best evaluation of the non-relaxed solution.

[chrispahm]

Alright, I tried to work in most of your suggestions (sorry for the delay). For updating the acceptableThreshold variable at every iteration I am not 100% sure on how to implement it, so here's a small gist displaying the issue I'm currently facing. Thanks for having a look!

[JWally]

@Toffi-123 this is slick! Thanks!

Sorry its take me so long to get around to this.

@bchevalier @lvenerosy does this step on anyone's toes with what you're working on?

[lvenerosy]

@JWally currently checking.