Prepare for class discussion an answer to the following exercises. Due date: December 13, 2010 (for the implementation in Comet of the 5th exercise the due date is December 17).
Make a Venn diagram (set diagram) representing the relation between the following classes of algorithms: construction heuristics (CH), metaheuristics (MH), local search (LS), stochastic local search (SLS), best improvement (BI), iterative improvement (II), first improvement (FI), uninformed random walk (RW), beam search (BS), rollout (RO), iterated greedy (IG), iterated local search (ILS).
Compare the pivot rules in tabu search and in simulated annealing. Think about computational issues and devise a guideline about the situations in which one or the other metaheuristic may be more appropriate.
Design a tabu search algorithm for the single machine total weighted tardiness problem using all three neighborhoods discussed in class.
Input: A set U of locations for n users, a set F of locations for m facilities and a distance matrix D=[dij] ∈ Rn× m.
Task: Select a set J ⊆ F of p locations where to install facilities such that the sum of the distances of each user to its closest installed facility is minimized, i.e.,
| min | ⎧ ⎨ ⎩ |
|
| dij | J ⊆ F and |J|=p | ⎫ ⎬ ⎭ |
Design a simple construction heuristic and a simple local search algorithm.
Consider the Max k-SAT problem and a local search on the one-flip neighborhood with best improvement strategy. Indicate which auxiliary data structures can be maintained to speed up each step. Provide a computational analysis. Implement them via invariants in COMET. Further, enhance your algorithm with metaheuristics.