In combinatorial optimization, on what type of problem a local search may lead to better & quicker solutions than usual mixed-integer programming and constraint programming techniques ?

By type of problem, I mean :

  • Field of application
  • Type of objective
  • Number and type of decision variables
  • Number and type of constraints
  • 4
    $\begingroup$ I think this question is too broad. There are just a huge number of factors that can affect the performance of heuristics vs. exact approaches. Also, what do you mean by "better and quicker"? -- heuristics will almost always be quicker and will, by definition, give better solutions. I would suggest editing this question to make it much more narrow, for example, ask about the effectiveness of heuristics or MIP for a specific type of problem or problem characteristic (e.g., number of constraints). $\endgroup$
    – LarrySnyder610
    Jun 9 '19 at 23:05
  • $\begingroup$ @LarrySnyder610 the question is indeed a bit broad. My goal with this question is explicitely to point out on which general kind of problems a local search may or may not perform well to help a potential reader to decide if it's worth trying to implement a local search on his specific optimization problem. There are clearly types of problems on which local searchs are unlikely to be effective or very difficult to implement (e.g. hard contrained problems) and other on which it's more likely to give good results (e.g. routing problems) $\endgroup$
    – Aral
    Jun 9 '19 at 23:51
  • 1
    $\begingroup$ THere's too much of putting on hold and closing questions on this site, IMO that should only be done for overwhelmingly compelling reasons, which I don;t believe hold in this case.Nor do I think close vs. reopen tug of wars are a good thing. $\endgroup$ Jun 10 '19 at 10:44

Those that you can't completely explore the branch-and-bound tree within your time limit. 😉 Don't forget you can do local search and large neighbourhood search in a branch-and-bound tree: fix some variables, solve, relax the fixings, fix other variables, solve, repeat. You get the best of both worlds with fast feasible solutions from a smaller search tree and dual bounds from MIP or propagation from CP.


Not the answer you're looking for? Browse other questions tagged or ask your own question.