DM86 Local Search Methods: Applications and Engineering
Study Plan for the Oral Exam

This is a list of possible questions that can be posed at the oral exam. Also available in PDF format.

Some questions require a re-organization of the knowledge that was given at the lectures. This is to stimulate an active and functional learning.

1. Make a concept map of the course.

2. Local Search Methods. Discuss. (what are they? when are they applicable? which are their pro and contra? which are the three sub-procedure recognizable? What are metaheuristics?)

3. Define Local Search Algorithms by introducing the 7 components in which they can be reduced.

4. Give an example of Iterative Improvement on the GCP, TSP, SMTWTP by defining the 7 components that constitute a local search algorithm.

5. Difference between objective and evaluation function. To which of the 7 LS components belongs the evaluation function?

6. The general idea behind the diverse construction heuristics:
   • for TSP: Nearest neighbor, Greedy heuristic on edges (multiple fragment heuristic), Greedy heuristic on vertices (Quick Borüvka), Insertion heuristics, Savings heuristics (Clark Wright), Christofides heuristic

   • for GCP: DSATUR, Recursive Largest First;

   • for SMTWTP: earliest due date, modified due date and apparent urgency heuristics

7. Which components must be defined and decisions taken to implement an Iterative Improvement algorithm? Which are the element of success?

8. Recall some speed up techniques for Iterative Improvement in TSP or GCP or SMTWTP.

9. Characterize the complexity class for local search algorithms named PLS. Does belonging to PLS mean that local search guarantees to reach local optima in polynomial time?

10. Neighborhood function and neighborhood operators for GCP, TSP and SMTWTP. Formalization and insight on the distance between solutions in the given neighborhoods are a plus.

11. Give a definition of search landscape and local optima. Which are the features of the search landscape that can affect a local search method? How?

12. Consider an Iterative Best Improvement for Graph Coloring under the approach $k$-fixed, complete improper colorings with one-exchange neighborhood. How is it possible to reduce the computational effort to examine the whole neighborhood to $O(\vert V^c\vert k)$, where $V^c$ is the set of vertices currently involved in a constraint violation? Which stored information is needed? Which is the complexity for initializing and updating this information after each one-exchange move?

13. Explain the phenomenon of phase transition in decision problems.

14. Give an high level procedure of one or more of the following Metaheuristics: Beam Search, Variable Neighborhood Descent, Variable Depth Search, Dynasearch, Randomized Iterative Improvement, Probabilistic Iterative Improvement, Simulated Annealing, Tabu Search, Dynamic Local Search Iterated Local Search, Greedy Randomized Adaptive Search Procedures, Adaptive Iterated Construction Search Ant Colony Optimization, Evolutionary Computation Algorithm, Scatter Search, Path Relinking, Cross Entropy Method.

    The procedure must be expressed in a correct algorithmic form.

    In answering these questions some few characterizing formulas must be known. These are: the Metropolis condition in simulated annealing, the utility and update function in guided local search, ant colony probabilistic pheromone-based construction, the update formula in Guided Local Search.

    Example of applications of these methods on the three toy problems of the course will be rewarded.

15. Classification of Local Search Methods (population based, nature inspired, etc.)

16. What is the configuration problem in local search methods and how can it be solved?

17. Sketch the Lin-Kernigham for TSP and the Dynasearch for SMTWTP (not required the details but only the main ideas).

18. Timetabling Problems. Discuss. (definitions, models, solution approaches, proximity with graph colouring)
19. Sketch a DSATUR based heuristic for timetabling
20. Neighborhoods structures and solution representations

21. Scheduling problems. Discuss. (definitions, problem classes, Problem classification formalism)

22. What are dispatching rules and how can they be devised?

23. The Flow Shop Problem. Solution representation, neighborhood relations, construction heuristics. Neighborhood reduction in the Novicki-Smutnicki Tabu Search.

24. The Group Shop Problem. Solution representation, neighborhood relations, construction heuristics. Critical operations and critical blocks, how they are defined in the solution representation and differences with the flow shop case.

25. Vehicle Routing Problems. Discuss. (Terminology, Classification and Models, differences with TSP)

26. Guiding principles of the construction heuristics for the CVRP (Savings, Nearest Neighbor, Cluster-Route)
27. Neighborhood structures for CVRP (through graphical representation).

28. Guiding principles of construction heuristics for VRPTW (saving heuristic, time-oriented nearest neighbors, insertion heuristics, time-oriented sweep heuristic).
29. Neighborhood structures for VRPTW (through graphical representation).
30. How is it possible to check local optimality in an OrOpt neighborhood in $O(n^k)$ instead of $O(n^{k+1})$ in TSPTW

31. Why there is the need for Statistics in the analysis of Local Search Algorithms?

32. Which are the summary measures and graphical visualizations adopted for Experimental Data Analysis?

33. Issues in Experimental Designs for Algorithms (which points are to be addressed and how?)

34. For each of the following cases:
    • Two samples
    • Two samples matched pairs
    • Single factor analysis of variance
    • Two factors analysis of variance
    • Two factors repeated measures Analysis of Variance
    • Multi factors analysis of variance
    Indicate schematically the experimental design, state the null and alternative hypothesis, and recall at least one parametric and one nonparametric statistical test.

35. Given that the computational experiments can last a certain amount of time due to practical constraints, how would you design the experiments?

36. Which are the assumptions underlying parametric tests? Are they reasonably attended in tests on algorithms? Which are the tools to detect deviations from the assumptions in ANOVA? Which are the possible remedies?

37. Describe the race algorithm and the statistical principles behind it.

38. Which issue exhibit Multiple Comparisons? Which adjustment of the level of confidence can be applied? Can you say something about these methods and their statistical power?