Kings College London 

This paper is part of an examination of the College counting towards the award of a degree. Examinations are governed by the College Regulations under the authority of the Academic Board. Degree Programmes Module Code Module Title Examination Period BSc, MSci 6CCS3OME Optimization Methods May 2017 (Period 2) Time Allowed Rubric Two hours ANSWER FOUR OF THE SIX QUESTIONS. ANSWER EACH QUESTION ON A NEW PAGE OF YOUR ANSWER BOOK AND WRITE ITS NUMBER IN THE SPACE PROVIDED. All questions carry equal marks 25 marks per question. If more than four questions are attempted, the answers to the rst four questions in exam paper order will count. Calculators are not permitted Books, notes or other written material may not be brought into this examination Calculators Notes PLEASE DO EXAMINATION ROOM 2017 King's College London NOT REMOVE THIS PAPER FROM THE May 2017 6CCS3OME 1. a. b. Describe, using pseudocode and comments, Dijkstra's single-source shortest-paths algorithm. Include in your answer the pseudocode of the initialisation step and operation Relax. [10 marks] The gure below depicts a snapshot of the computation of Dijkstra's shortest-path algorithm. Vertex s is the source vertex. The snapshot is taken at the beginning of the sixth iteration, when the ve vertices s, e, g, h and f have already been considered. The numbers next to these vertices are their current shortest-path estimates. Show the current shortest-path estimates and the Parent vertices for the vertices a, b and c. d[f]=8 f 7 e d[g]=6 2 29 g 6 d[c]=? c Parent[c]=? a5b2 d[a]=? Parent[a]=? d[b]=? Parent[b]=? 4 8 d[e]=4 9 s d[s]=0 4 3 6 hd[h]=7 3 c. The reliability of a path v1,v2,...,vk in a directed graph G = (V,E), is dened as the product p(v1, v2)p(v2, v3) p(vk1, vk), where p(v, u) is the probability that edge (v,u) does not fail. Suppose that p(v,u) is known for each edge (v,u) in G and 0 < p(v,u) 1. Describe how we could compute for two given nodes s and t in G a path from s to t with the highest reliability. [5 marks] Page 2 SEE NEXT PAGE [10 marks] May 2017 6CCS3OME 2. a.Describe,usingpseudocodewithcommentsorplainEnglish,theecient shortest-path algorithm for directed acyclic graphs which was discussed in class. State and justify the running time of this algorithm. [10 marks] b. Trace the execution of the algorithm from Question 2.a on the graph shown below. Show the shortest-path estimates of all nodes and the tree represented by the Parent array at the beginning of the iteration when node c is considered; at the end of the computation. 2 a 5 c 3 p 1 6 1 2 v source s 4 3 b 1 2 k d 4 c. Assume that the shortest-path weights and a shortest-paths tree have been computed for a given graph G with a source node s and possibly negative edge weights. Now one edge, which happens to be a tree edge, is removed from the graph and we want to re-compute the shortest- path weights and a shortest-paths tree. How should the "Bellman-Ford with FIFO" shortest-path algorithm be re-started to re-use some data computed before? Support your explanations by referring to the graph G in the diagram below, where bold arrows indicate the computed shortest- paths tree and (x, y) is the tree edge which is about to be removed. u a g b p h [10 marks] s c x y [5 marks] Page 3 SEE NEXT PAGE May 2017 6CCS3OME 3. a. We are computing an allocation of six tasks T1,T2,...,T6 to six employees E1,E2,...,E6 (one task per one employee) using the Edmonds-Karp maximum-ow algorithm. The ow after ve iterations is shown on the diagram below. Explain the computation and the updates made during the next, sixth iteration. Show the computed nal allocation of tasks to employees. s T1 T2 T3 T4 T5 T6 E1 E2 E3 E4 E5 E6 t b. Explain how we can bound the number of iterations of the Ford- Fulkerson method for computing maximum ows in networks with inte- gral capacities. Explain how we can use this bound to derive the running time of the computation of the algorithm from Question 3.a in terms of the number of tasks p, the number of employees q and the number m of pairs (T i, Ej) indicating that task T i can be done by employee Ej. QUESTION 3 CONTINUES ON NEXT PAGE Page 4 SEE NEXT PAGE [15 marks] [5 marks] May 2017 6CCS3OME c. Consider the following extension of the basic scenario of allocating tasks to employees. Each employee can participate only in one task (as in the basic scenario), but now the same task Ti can be allocated to up to ki dierent employees, where ki 1 and all numbers ki are known. (For example, the same task T1 of deploying the same system update can potentially be done for up to k1 dierent clients, so can be allocated to up to k1 dierent employees.) The objective is to compute the task allocation so that the number of employees with allocated tasks is max- imized. Could this problem be solved by an appropriate network ow algorithm? Explain your answer. [5 marks] Page 5 SEE NEXT PAGE May 2017 6CCS3OME 4. a.Describe,usingpseudocodeandcomments,thesuccessiveshortestpath algorithm for the minimum-cost ow problem. Include a description of how the ow is updated in each iteration. [15 marks] b. An instance of some production-distribution problem is modeled as an instance of the minimum-cost ow problem depicted below. The two numbers next to an edge are the capacity of this edge (the rst number) and the cost of one unit of ow on this edge (the second number). The number at a plant node pi is the maximum production (the supply) at this plant. The number at a retail-centre node ri indicates the demand. Trace the execution of the rst and second iterations of the successive shortest path algorithm on this instance of the minimum-cost ow prob- lem. Assume that whenever there is a choice of nodes, the smallest node in the lexicographical order is selected. (For example, p1 before p2.) Show the paths selected in the rst and second iterations. Show also the ow on the edges of the network at the end of the second iteration. (60, 50) p1 (80, 45) (90, 40) (90, 0) 100 r2 90 [10 marks] p1/m1 p1/m2 (80, 6) (60, 5) p2/m1 (80, 5) (90, 6) r1/m1 r1/m2 r1 +70 (70, 40) (80, 5) (70, 0) p2 +120 r2/m1 (70, 0) (60, 5) (50, 5) (80, 7) (40, 0) p2/m2 r2/m2 Page 6 SEE NEXT PAGE May 2017 6CCS3OME 5. a. b. c. Explain the notion of a combinatorial optimisation problem. Give two examples of combinatorial optimisation problems. Show how your example problems t within the framework of combinatorial opti- misation problems. [7 marks] Explain the notions of partial conguration and bounding procedure in the context of the branch-and-bound method. [6 marks] Let a partial conguration for the traveling salesman problem be any initial segment of a tour starting with city 1. i. Describe a bounding procedure which could be used in the branch- and-bound method for the traveling salesman problem. [6 marks] ii. Show the bound which the bounding procedure you have given in 5.c.i returns for the input given in the table below and the partial cong- uration 1, 5, 3. 12345 1 0715910 2 90 8311 345078 4117 90 6 5189 74 0 Page 7 SEE NEXT PAGE [6 marks] May 2017 6CCS3OME 6. a.Explaintheconceptoflocalsearchforasolutiontoagivencombinatorial optimisation problem. Explain the notion of local optimum in the context of the local search for combinatorial optimisation problems. [5 marks] b. Explain how the simulated annealing method deals with the issue of local optima. Does the simulated annealing method compute the global optimum so- lution? Justify your answer. c. Dene the weighted graph bisection problem. [8 marks] [5 marks] d. To apply the genetic algorithms metaheuristic to a combinatorial opti- misation problem, we have to dene a crossover operation on congura- tions. Explain the diculties of designing a 1-point crossover operation for the weighted graph bisection problem. [7 marks] Page 8 FINAL PAGE