Applications of Tabu Search opim 950 Gary Chen

Yüklə 0,57 Mb.
ölçüsü0,57 Mb.

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


  • 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:

  • 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


  • 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


  • Rj(x) = length of jth district boundary

  • R = perimeter of entire territory

Socio-Economic Homogeneity

Similarity to Previous Districting

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

  • A = Entire territory area


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.

  • 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.



  • 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.

Yüklə 0,57 Mb.

Dostları ilə paylaş:

Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur © 2024
rəhbərliyinə müraciət

    Ana səhifə