09 07 19

Page 1

Nome: Cognome: Matricola : Exam 19/7/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 starting from root 1. Specify what is most efficient algorithm for this type of graph, and apply it illustrating the intermediate steps, and a possible preprocessing phase. 3 5 21 4 67 3 1 5 10 3 6 1 2 2 3 2 3 10 Additional question Once the solution has been found, determine for arc (4,2) what is the largest length coefficient for which the shortest path tree remains unchanged (same arcs in the solution, though some of the node labels may change). Justify the answer. 2. Given the following linear programming problem: max −2x1 +x2 −4x1−x2 ≤ 2 2x1 + 6x2 ≤ 16 −2x1 + 2x2 ≤ 7 −x2≤ 0 consider the solution ¯x = [ −1/2 0 ] . Write the conditions of existence and nonexistence of a growing feasible direction in ¯x and represent the two conditions geometrically. Determine which of the following directions is a growing feasible direction: ξ′ = [ −1 0 ] and ξ′′ = [ −1 4 ] . Justify your answer. 3. Consider the following integer linear programming problem max x1 + 2x2 −4x1 + 5x2 ≤ 10 2x1 + 2x2 ≤ 7 x1,x 2∈Z + Add the slack variables (x3 andx4) to the first and the second constraints, and consider the optimal baseB ={1, 2} of the LP relaxation. Generate the Gomory cuts associated with the fractional components of the solution. Justify your answer and give the geometric representation of the feasible region and of the cuts. 4. Consider the following ILP problem in n variables: P : max{cx : Ax≤ b,x ∈ Zn +} and its LP relaxation ¯P : max{cx :Ax≤b,x∈ Rn,x≥ 0}. Let ¯x be the feasible solution of…