Detour: Combinatorial Optimization

Lecture on 18.10.2007

Presentation

This lecture was a bit of a detour to establish some concepts needed to understand some other important concepts in the rest of the course.

Combinatorial Optimization is informally defined as finding the best solution to a problem from a finite set of possible solutions. We established some basic definitions, looked at a few classic optimization problems, and then looked at several heuristic algorithms used to solve these.

(Special thanks to Arjun Chandra for his notes on combinatorial optimisation from our MSc in Natural Computation at Birmingham University)

Pretend that you are going to go on four dates with four different girls, and have to choose which restaurant to take each one to. You will only go on one date with each girl, and you can only go to a restaurant once. Given that the number in the table represents how happy the girl will be if she goes to the corresponding restaurant, which girls should you take to which restaurants to maximize the total happiness for everyone?

This is a good example of a combinatorial optimization problem, in which there is a finite set of possible solutions.

* Total number of possibilities: 4! = 4*3*2*1 = 24

• list of cities needs to be visited, only once to each city, return to point of start
• Real Life Example: Traveling salesmen, postmen, Lorry routing, etc

• Given a boolean sentence, is there an assignment of variables such that the sentence is true?
• example: E = (x1 OR x2) AND (x1 OR NOT(x2)) → Yes, can be solved (solution: x1 = TRUE)
• CNF vs DNF
• This is an important problem because it has been proved that any NP-complete problem can be translated into a SAT problem.

• Given a list of items with a value and weight, what is the set of items with the maximum value within a certain weight?
• Optimized usage of capacity
• Real Life Example: Containers on ships, trucks, etc

• Given a graph G, a vertex cover is a set of vertices that contains at least one endpoint of every edge in the graph.
• Real Life Example: Determination of best Hotspot-location for Wifi, warehouse layout, mobile cells, …

• does not use domain knowledge
• Many nature-inspired algorithms are BB

• the number of time the fitness function is used
• O(n)

• Easy to apply to different problems - plug 'n' play

• Does not take advantage of domain knowledge, and thus can be potentially less efficient than applied solutions

Local search is a “meta-heuristic” that many algorithms use to solve problems. It is based on the concept of a “neighborhood” around a given candidate solution (usually given as N(x)), which is usually dependent on the specific algorithm in use.

  1. Pick random x ∈ X
  2. Pick y ∈ N(x) where f(y) >= f(x)
  3. Let x := y
  4. Goto 2

Hill climbing is a simple implementation of local search where often you choose the best candidate in the neighborhood of x. In a two-dimensional example, this can be compared with walking in the mountains and always looking around in a 5m radius and going in the direction that is the steepest (which is usually referred to as steepest ascent hill climbing).

Tabu search is a local search algorithm based on the social concept of “taboos”, or things that you don't talk about in polite society. It is dependent on a “Tabu list”, which is a time-limited list of operators that you have used to generate the neighborhood around x; for example, if your solution representation is a bitstring, an “operator” in this case might be “flip the first bit”. When generating the neighborhood of the next point, you do not use any operators that are in the Tabu list.

However, in some cases you want to ignore the list, for example if you are caught in a cycle or have not seen any fitness improvement in a long time. The criteria for ignoring the Tabu list are called the “Aspiration Criteria”.

   1. Let tabu list T := {}
   2. Pick random x ∈ X
   3. Generate all neighbors of x, except those generated by operators in T
   4. Let x := y, where y is best neighbor
   5. Add operator x -> y to T
   6. Remove from T any operators that have been there longer than a certain time (tenure)
   7. Goto 3