4 ms·

I 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 h

I 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 ago
I'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 ago
  Yeah, 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 ago
    Only 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 ago
      I 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.

_raoulcousins 9y ago

I'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 ago
Yeah, 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 ago
  Only 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 ago
    I 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.