7. Meta-heuristics: several previous problems

A meta-heuristic is a canvas or framework to construct a heuristic adapted to your specific problem. Dozens of meta-heuristics have been invented. Let’s set aside the unproductive debate about what meta-heuristic is best and who invented it and let’s dive right into the topic. Meta-heuristics:

• are quite new: the first ones were designed in the 1960s;
• are not very well understood: why are some efficient for some problems but not for others?;
• are somehow all interrelated: you can express one meta-heuristic with another;
• have their efficiency heavily depending on the quality of the code as well as the knowledge of the problem.
• are often based on very simple ideas.

One could write books on meta-heuristics and indeed lots of books, articles and reports have been written. There are even scientific communities that only swear by this meta-heuristic and each meta-heuristic comes with its own vocabulary[1]. In this manual, we only scratch the surface of this fascinating subject.

Many meta-heuristics are based on Local Search[2]: they start with an initial solution and improve it little by little. From now on and for the rest of this chapter, we only talk about meta-heuristics using Local Search.

Warning

The whole chapter is about meta-heuristics using Local Search.

Among them, we present three well-known meta-heuristics:

• Tabu Search: one of the most efficient meta-heuristic on the market!
• Simulated Annealing: one of the first available meta-heuristic.
• Guided Local Search: well suited for some problems like Routing Problems.

These three meta-heuristics are implemented in or-tools and are used in the routing library (through flags).

In or-tools, we implement meta-heuristics with SearchMonitors guiding Local Search (and thus we also use the LocalSearch, LocalSearchOperator, LocalSearchFilter classes). This is quite “natural” as SearchMonitors allow to... monitor the search and the implemented meta-heuristics are based on Local Search.

When you implement a (meta)-heuristic, you have to take decisions. Our implementations are one possibility among others. We would like to warn the reader on an important choice we have made in our implementation: we only use meta-heuristic when we have reached a local optimum, not before!

Warning

Our meta-heuristics only kick in when we already have reached a local optimum with the Local Search.

A last word of advice. In this chapter, we decided to show you the code in full details. Real code, especially in optimization, is complicated and has to deal with lots of subtleties. While we try to explain most of the intricate details (but not all), you only see the end results. The code we show has been polished and is used in production (and changes sometimes!). Some parts have a long history of trial and error and there is no way we can explain all the details. We cannot emphasize enough that you’ll learn how to use the or-tools by actually coding with it, not only reading existing code. That said, the exposed code gives you good examples on what can be done and how the makers of the or-tools library decided to do it. Beside, you’ll have a pretty good idea of what actually our meta-heuristic implementations do and how to adapt the code to solve your problems.

Overview:

Before diving in the heart of the matter, we address two ways to improve the search. First, because our meta-heuristics never stop, we detail how SearchLimits can be used to stop a search. Second, we discuss restarting a search. Recent research shows that restarting a search might improve the overall search. Next, we detail our Metaheuristic class and our three specialized TabuSearch, SimulatedAnnealing and GuidedLocalSearch implementations. To finish this chapter, we present another meta-heuristic, Large Neighborhood Search[3], that is not implemented with a SearchMonitor but with a LocalSearchOperator. Next we answer the question “What do you do when you have no idea of a (good) search strategy?”. Answer? You throw in lots of heuristic and random behavior in your top-level search. In or-tools, we implemented the DefaultIntegerSearch DecisionBuilder to do just that.

Prerequisites:

• Basic knowledge of C++.
• Basic knowledge of Constraint Programming (see chapter Introduction to constraint programming).
• Basic knowledge of the Constraint Programming Solver (see chapter First steps with or-tools: cryptarithmetic puzzles).
• The section Basic working of the solver: the search algorithm helps but is not mandatory.
• The chapter Local Search: the Job-Shop Problem about Local Search as this chapter heavily depends on Local Search. Most of our examples involve the Job-Shop Problem.

Classes under scrutiny:

SearchLimit, SearchMonitor, Metaheuristic, TabuSearch, SimulatedAnnealing, GuidedLocalSearch, LocalSearchOperator and DefaultIntegerSearch.

Files:

The files used in this chapter are:

• limits.h: This header file contains several search limits. This file is used throughout most of the examples of this chapter.
• jobshop_ts1.cc: The same as file jobshop_ls1.cc from the previous chapter but with Tabu Search added.
• jobshop_ts2.cc: The same as file jobshop_ls3.cc from the previous chapter but with Tabu Search added.
• jobshop_sa1.cc: The same as file jobshop_ls1.cc from the previous chapter but with Simulated Annealing added.
• jobshop_sa2.cc: The same as file jobshop_ls3.cc from the previous chapter but with Simulated Annealing added.
• dummy_lns.cc: The basic example solved with Large Neighborhood Search.
• jobshop_lns.h: a basic SequenceLns LocalSearchOperator to solve the Job-Shop Problem with Large Neighborhood Search.
• jobshop_lns.cc: A basic implementation of Large Neighborhood Search with the SequenceLns LocalSearchOperator to solve the Job-Shop Problem.
• jobshop_heuristic.cc: We use all the previous ingredients to solve approximately the Job-Shop Problem.
• golomb_default_search1.cc: We solve the Golomb Ruler Problem with Default Search.
• golomb_default_search2.cc: Same as golomb_default_search1.cc but with customized DefaultPhaseParameters parameters.

Content:

• 7.1. Search limits and SearchLimits
  • 7.1.1. An example of a custom Searchlimit: NoImprovementLimit
  • 7.1.2. A callback to catch the CTRL-C interrupt
• 7.2. Restarting the search
  • 7.2.1. Constant Restart
  • 7.2.2. Luby
  • 7.2.3. NoGoods
• 7.3. Meta-heuristics in or-tools
  • 7.3.1. The basic idea
  • 7.3.2. The Metaheuristic class
  • 7.3.3. Interesting callbacks from the SearchMonitor class
  • 7.3.4. Implemented meta-heuristics in or-tools
• 7.4. Tabu Search (TS)
  • 7.4.1. The basic idea
  • 7.4.2. Our implementation
  • 7.4.3. First results
• 7.5. Simulated Annealing (SA)
  • 7.5.1. The basic idea
  • 7.5.2. Our implementation
  • 7.5.3. First results
• 7.6. Guided Local Search (GLS)
  • 7.6.1. The basic idea
  • 7.6.2. Our implementation
  • 7.6.3. GuidedLocalSearchPenalties
  • 7.6.4. The abstract GuidedLocalSearch class
  • 7.6.5. The real classes
  • 7.6.6. Guidelines to write your own GLS
• 7.7. Large neighborhood search (LNS): the Job-Shop Problem
  • 7.7.1. What is Large Neighborhood Search?
  • 7.7.2. Large Neighborhood Search in or-tools
  • 7.7.3. Interesting LNS operators
  • 7.7.4. A heuristic to solve the job-shop problem
• 7.8. Default search
  • 7.8.1. Impact based search strategies
  • 7.8.2. DefaultPhaseParameters
  • 7.8.3. First results
• 7.9. Summary
  • 7.9.1. A little word on the efficiency of meta-heuristics

Footnotes

[1]

In order to “sell” your (meta-)heuristic to the scientific community, it is also good to give it a snappy name. We don’t resist to name a few: artificial bee colony algorithm, honey-bee mating optimization, intelligent water drops, firefly algorithm, monkey search, league championship algorithm, cuckoo search, virus optimization algorithm, galaxy-based search algorithm, ... and our favorite: the imperialist competitive algorithm.

[2]

Local Search and meta-heuristics are so intricate that it is difficult to separate the two concepts. This is also the case in the or-tools library. The LocalSearch class was devised with the Metaheuristic class in mind and vice-versa. Reread the section What is Local Search (LS)? if needed. It also has some comments on meta-heuristics in general. Because we use Local Search, most of the examples will involve the Job-Shop Problem and the implementation of the LocalSearchOperators met in the previous chapter.

[3]	Large Neighborhood Search (LNS) can be seen as a meta-heuristic (same for Local Search) and is in a way an extension of Local Search. In or-tools, we implement LNS with special LocalSearchOperators.