5 ms·
Google has a very nice suite of optimization tools, including an integer programming solver and a constraint solver, for third party use. Docs here: https://dev
by obstinate 9y ago
Google has a very nice suite of optimization tools, including an integer programming solver and a constraint solver, for third party use. Docs here: https://developers.google.com/optimization/ https://developers.google.com/optimization/ I got a chance to use it at work lately and it really is magical how you input a problem description and it outputs a solution.
The documentation is hit or miss in some cases. MPSolver is pretty well documented. The more powerful constraint solver . . . well, I have no idea how to use the SA or Tabu search features, and minimal confidence that I'm doing anything correctly, except that it seems to emit correct-ish answers.
- beagle3 9y agoSA and Tabu are both heuristic, so you're never going to get anything but correct-ish answers (definitely no guarantee of THE correct answer).
- hartror 9y ago!correct-ish optimal-ish
- obstinate 9y agoI think you mean that they will not necessarily find optimal solutions, at least when the problem size is large. I understand that. What I don't understand is how to verify that they're giving me anything better than local search. I also don't have the background to know what settings to use (initial temperature in the SA case or the similar setting for Tabu search) nor which heuristic better suits my problem.
- _raoulcousins 9y agoI'm not familiar with Google's particular implementation of these, but with the right value of the parameters, they are equivalent to local search. You could test with these parameters and see if the solution changes. In the simplest implementation of Tabu Search, a maximum tabu list length of zero will never reject any candidates. A simple simulated annealing should become a naive local search if the probability of rejecting a candidate solution is zero. As far as which heuristic is better: I'd avoid premature optimization when solving optimization problems. Pick one, and if you're satisfied with the results, then go with it? Academics usually test their heuristics against benchmark problem instances with known optimal solutions (or if no optimal solution is known, best known upper bounds). That would be a bit more thorough.
- obstinate 9y agoYeah, I think the main issue is that I have only tested on pessimal problems so far. In this case, I'm only able to find one or two solutions before I run out of time to iterate, so neither Tabu nor SA are giving me much. Monday I'll be doing some more testing on realistic problems and I'll be able to get a better idea of which solution is best. Or maybe I'll find that I don't need heuristics at all, since the real problems may have a much lower branching factor than my pessimal case.
- _raoulcousins 9y agoOnly one or two feasible solutions? That's a little suspicious, but in general feasibility isn't any easier than optimality. If you'd like to talk optimization/metaheuristics feel free to shoot me an email (in my profile). I have a fair bit of experience with them so I might be able to point you in the right direction.
- obstinate 9y agoI only have a few milliseconds to do the search. I erred in what I said though. I find one or two improvements on the initial result during the time I have allotted. I'd reach out, but I doubt the company would approve of talking to a third party about the details of internal work. We also have some experts internally who I can talk to if I get stuck. :) Thank you for the kind offer, though.
- R_haterade 9y agoDefinitely true, and the lack of distinction drives me insane sometimes. However, describe this distinction to the average executive and tell us how it goes. :-)
- learc83 9y agoThe solution presented in the article also wasn't guaranteed to be THE correct answer.