7
$\begingroup$

I am working through Pascal Van Hentenryck's excellent discrete optimization course on Coursera.

While the course certainly touches on it in some ways, I am looking for more of a framework in terms of what kinds of solutions are likely to work well where? For example, when would I use local search vs a mixed integer program? If I am using local search, when would I use tabu search rather than simulated annealing?

$\endgroup$

2 Answers 2

9
$\begingroup$

You have to keep in mind that MIPs can return the optimal solution, provided enough computation time is given. So if time is not an issue, I would always go for a MIP. Also, MIPs are more flexible in the sense that you can very easily add new constraints, modify the objective function, etc.

On the other hand, with metaheuristics such as local search, there is no guarantee that you will reach optimality, and you might spend a lot of time designing your algorithm which may not work anymore if you need to add a new constraint. That said, they are a great alternative if computation time is an issue. And in practice, computation times are easily an issue if you are working on large data sets.

The choice of the metaheuristic is, I think, a matter of taste (and trend) more than anything. I was told as a student years ago that simulated annealing is no longer considered as an efficient local search technique, and yet it is still used here and there. Perhaps a good way of choosing your algorithm is to find papers where the authors show that their technique worked on the considered type of problem. For example, there are many papers such as this one showing excellent results with Tabu Search for graph coloring.

Regarding trend, there is a famous article called Ants can color graphs from 1997. The article is fascinating, the authors show how you can implement efficient algorithms with artificial ants. But I am pretty sure that if you asked the authors what they think of their article today, they would agree that it was a lot of fun, but they would not use this technique anymore. At the time, using ants was trendy!

$\endgroup$
1
  • 3
    $\begingroup$ One other virtue of MIPs: they provide bounds on the objective, which allow the user to assess how far off a solution might be if the MIP is terminated before proof of optimality. The bounds are not always tight enough to be helpful, but they are often (usually?) better than nothing. $\endgroup$
    – prubin
    Jan 14, 2022 at 16:29
10
$\begingroup$

Here are my notes about the various discrete optimization methods.


Combinatorial branch-and-bound

  • Manual implementation
  • Provides a bound
  • Works well when the bound is good
  • Rarely used nowadays

Mixed-Integer (Non)-Linear Programming

  • Model-and-run, very good commercial solvers
  • Provides a bound
  • Works well when the (N)LP relaxation (possibly with cuts) is good (i.e. not too many big-M constraints)
  • Handles continuous variables
  • It might be difficult to express some components of the problem with only (non)-linear equations (e.g. scheduling constraints)

Constraint Programming

  • Model-and-run, but might require manual tweaks
  • More expressive modelling language, it might be easier to model some complex constraints
  • On the other hand, it's easy to get lost in all the available constraints
  • Doesn't provide a bound during the search, but proves the optimality at the end
  • Works well on problems with many constraints
  • Robust to the addition of constraints
  • Not robust to changes in the objective

Local search

  • Model-and-run with LocalSolver, otherwise manual implementation
  • Heuristic approach
  • Works well on large problems without too many constraints
  • Robust to changes in the objective
  • Not robust to the addition of constraints

Tree search

  • Manual implementation
  • Proves the optimality on small instances
  • Works well on problems with many constraints, good dominances, and when it is simple enough to assess the quality of a partial solution
  • Doesn't work well if a bad decision can be taken early without noticing it
  • Robust to the addition of constraints
  • Not robust to changes in the objective

Large neighborhood search

  • Already implemented inside some CP/MILP/MINLP solvers, otherwise manual implementation
  • Heuristic approach
  • Works well on large problems with many constraints
  • Handles continuous variables if the constructive component does

Note 1: if you work in academia, your criteria will certainly be "solution quality" and "computation time". If you work in industry, you also need to consider development time, maintainability and flexibility.

Note 2: simulated annealing, tabu search, guided local search, iterated local search.. are all variants of local search. You should be able to get good results with any of them if local search works well for your problem. If you don't have more intuition, pick the one you're the most comfortable with. I just wouldn't recommend simulated annealing since it's the hardest one to calibrate and I don't know any problem on which it's state-of-the-art

$\endgroup$
1
  • $\begingroup$ A very helpful summary indeed. $\endgroup$
    – dkent
    Feb 24, 2022 at 12:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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