King’s 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, BEng, MEng
6CCS3OME Optimisation Methods May 2019
Time Allowed Rubric
Two hours
Answer all questions 1–8 and 13-14. Answer either ques- tions 9–10, or questions 11–12.
If both questions 9–10 and 11–12 are attempted, only 9– 10 will be marked. Questions not to be marked must be struck through with a line on the answer sheet.
The multiple-choice questions have ONE or MORE cor- rect choices. In order to obtain full marks you must select all correct choices and only those.
Marks will be deducted for incorrect choices se- lected in those questions.
Questions 1–8 each carry FIVE marks. Questions 9–14 each carry FIFTEEN marks.
The answers to questions 1–12 need to be clearly made by pen on the appropriate grid on the answer sheet provided at the back of the exam paper. The answers to questions 13–14 need to be written by pen on the separate answer book provided.
Calculators may be used. The following models are permit- ted: Casio fx83 / Casio fx85.
Books, notes or other written material may not be brought into this examination
Calculators Notes
PLEASE DO NOT REMOVE THIS PAPER FROM THE EXAMINATION ROOM
2019 King’s College London
May 2019 6CCS3OME
13. The diagram below shows a flow network for a USA based transportation company. In this diagram, a flow f is shown, with the source node denoted s, the sink (target) t, and intermediate nodes with letters between a to f. The two numbers next to each edge denote the amount of flow in that edge, and the capacity of the edge in parentheses.
a. In the context of network flow problems, define and provide the formula for each of the following terms.
1. Value of a flow,
2. Flow conservation, 3. Saturated edge.
[3 marks]
b. What is the value of the flow in this figure? Show a decomposition of this flow into possible flow paths.
[3 marks]
c. Does this graph show a maximum flow? Using the max-flow min-cut theorem, explain if the flow shown in the figure is a maximum flow?
[5 marks]
d. The capacity of the edge (a, d) is increased by from 2 to 3. Starting from the flow given in the figure above, construct a residual network, and use the Edmonds-Karp algorithm to compute the maximum flow. Show your working.
[4 marks]
Page 20
SEE NEXT PAGE
May 2019 6CCS3OME
14. a.Explainthefollowingnotions,whichappearinthecontextofthebranch- and-bound method:
1. partial configuration, 2. branching procedure, 3. bounding procedure.
[5 marks]
b. Let a partial configuration for the travelling salesman problem be any initial segment of a tour.
1. Describe a bounding procedure suitable for use in the branch-and- bound method for the travelling salesman problem.
2. Show the bound which your bounding procedure returns for the input given in the table below and the partial solution ⟨1, 2, 3⟩.
12345 1
2 3 4 5
0 10 15 4 20 90836 4 5 0 7 16
11 7 9 0 2 18 9 6 4 0
Page 21
FINAL PAGE
[10 marks]