Applications of Tabu Search opim 950 Gary Chen

Applications of Tabu Search

• OPIM 950

• Gary Chen

• 9/29/03

Basic Tabu Search Overview

• Pick an arbitrary point and evaluate an initial solution

• Compute next set of solutions within neighborhood of current solution

• Pick best solution from the set.

• If solution is on Tabu (or forbidden) list, pick next best solution. Repeat until you come across solution not on Tabu list.

• After solution is chosen, repeat from step 2 until optima is reached.

• Parameters for tuning: Number of iterations, penalty points, size of Taboo list

Applications

• Bioengineering

• Finance

• Manufacturing

• Scheduling

• Political Districting

• Many of the applications of Tabu Search are very similar to Simulated Annealing

Application 1: Student Course Scheduling

• Problem: Registering for classes required students waiting in long queues.

• Solution: Allow course registration over the internet and using OR techniques (tabu search), give student satisfactory time schedule as well as balance section loads.

Objectives and Constraints

• Main Objective: Find conflict-free time schedule for each student

• Secondary Objectives:

• Balance number of classes per day
• Minimize gaps between classes
• Respect language preferences

• Student course selections must be respected

• Section enrollment must be balanced

• Section maximum capacity cannot be exceeded

Implementation - Part 1

• Construct student timetable without considering section enrollments

• Model course sections as undirected graphs

Maximum Cardinality Independent Sets

• Objective: Find sets that contain one section of each course.

• Algorithm

• Find all cliques in the graphs.
• Pick one node or no nodes from each clique. Check if it’s a valid schedule. If it is retain as a possible solution set.
• repeat

Implementation - Part 2

• Balance out section enrollment

• Each student has a set of possible time schedules.

• “Optimal” time schedule for a student adheres to following criteria:

• Balance number of classes per day
• Minimize gaps between classes
• Respect language preferences

Tabu Search

• Objective: Find satisfactory course schedule.

• “Satisfactory” being a solution no more than a threshold cost distance from the “optimal” course scheduling.
• Tabu list contains previously tried student course schedules.

• Tabu search combined with strategic oscillation used.

Strategic Oscillation

• Perform moves until hitting a boundary.

• Modify objective constraints or extend neighborhood function to allow crossing over to infeasible region.

• Proceed beyond boundary for a set depth

• Turn around to enforce feasibility

Strategic Oscillation (Cont)

• For course selection, class size is strategically oscillated.

Application 2: Tabu Search for Political Districting

• Problem: Partition a territory into voting districts. Political influence problems.

• Solution: Using tabu search for deciding districts will result in a fair, unbiased answer

Constraints

• Districts should be contiguous

• Voting population should be close to evenly divided among the districts

• Natural boundaries should be respected

• Existing political subdivisions, such as townships, should be respected

• Socio-economic homogeneity

• Integrity of communities should be respected

General Solution Strategy

• Clustering approach

• First pick several pre-determined centroid districts.
• “Grow” districts outward.

• Previous attempts

• Branch-and-bound trees (NP-hard)
• Simulated annealing

Problem Formulation

• minimize

• i are user-supplied multiplers

• fpop(x) = population equality function

• fcomp(x) = compactness function

• fsoc(x) = socio-economic homogeneity function

• fsim(x) = similarity to previous districting function

• fint() = integrity of communities function

Population Equality

Compactness

• Rj(x) = length of jth district boundary

• R = perimeter of entire territory

Socio-Economic Homogeneity

• Sj(x) = standard deviation of income in district j.

• = average income in entire territory

Similarity to Previous Districting

• Oj(x) = largest overlay of district j and similar district in new solution

• A = Entire territory area

Example

Integrity of Communities

• Gj(x) = largest population of a given community (Chinese, latino, etc) in district j.

• Pj(x) = total population in district j.

Tabu Search

• Start with initial solution

• Start with a seed unit for initializing a district.
• “Grow” district by merging it with adjacent units until reached or no adjacent unit are available.

Tabu Search (cont)

• After initial solution created, two possible moves.

• Give – give a basic unit from one district to another
• Swap – swap basic units along boundary of two adjacent districts

• Any basic units swapped or given are placed on a tabu list.

• Algorithm stops when value of current best solution has no improvements from previously known best solution.

Example

References

• Alvarez-Valdes, R. et al. Assigning students to course sections using tabu search. Annals of Operations Research. Vol. 96 (2000) p. 1-16

• Bozkaya, Burcin. A tabu search heuristic and adaptive memory procedure for political districting. European Journal of Operational Research. Vol. 144 (2003) p. 12-26.