31 01 19

Page 1

Nome: Cognome: Matricola : Exam 31/1/2019 First part : Closed book Total score: 21 pts. Minimum score to pass: 11 pts. Tentative scores: 1) 4 pts, 2) 5 pts, 3) 5 pts, 4) 3 pts. 5) 4 pts. 1. Consider the directed graph in the figure below, with lengths reported on the arcs. Compute the shortest path tree with root in node 1, after a possible pre processing phase, using the most efficient algorithm. Illustrate the intermediate steps. What is the complexity of the algorithm in terms of the input size? 3 5 2 1 4 6 70 0 0 1 -4 1 -2 1 -1 1 2 2. Consider the following linear programming problem: max 2 x1 + x2 2x2 ≤ 9 −3x1 + 2x2 ≤ 6 3x1 + x2 ≤ 12 −4x2≤ 9 for each of the following subsets of indices determine if they define a basic solution, and in case they are a basic solution discuss their primal feasibility and their dual feasibility: B1 ={1, 4}, B2 ={2, 3}, B3 ={1, 3}. 3. Consider the following 0-1 knapsack problem max 35 x1 + 21x2 + 11x3 + 9x4 + 3x5− 6x6 7x1 + 5x2 + 4x3 + 2x4− 3x5 + x6≤ 8 xi∈{ 0, 1} Compute the optimal solution by applying the Branch and Bound algorithm that uses the linear relaxation to estimate an upper bound. Compute an initial feasible solution by applying the greedy algorithm. Report the computation of the upper bound at each iteration and the enumeration tree. Apply the fixing of variables whenever it is possible. 4. Consider the following ILP problem in n variabes: P : max{cx : Ax≤ b, x∈ Zn +} and its LP relaxation ¯P : max{cx : Ax≤ b, x∈ Rn, x≥ 0}. Which of the following statements is true? Justify the answer. i) The feasible region of the relaxation ¯P is a subset of the feasible region of P . ii) If the optimal solution of ¯P has all integer components then the value of the optimal solution in P and ¯P is equal. iii) if the optimal solution ¯x of ¯P…