ORIE 5380 / CS 5727 - Makeup Exam

Andrea Lodi February 13, 2022

1. (7 points) Consider the following general form LP (where A has m rows), min cT x

x

s.t. Ax ≥ b

Convert it to a standard form LP, that is, choose c′, A′ and b′ while introducing slack variables if needed such

that this problem is equivalent to

2. (12 points) Consider the LP

min (c′)T x x

s.t. A′x = b′ x≥0

max x1 +3x2 +x3 +9x4 x1 ,x2 ,x3

s.t. 8x1 +2x2 +4x3 +3x4 ≤ 12 x1,x2,x3 ≥0

(a) (6 points) Derive its dual.

(b) (2 points) Give the solution to the dual LP by observation, without performing the Simplex method.

(c) (4 points) Given your solution to the dual, use complementary slackness to derive the optimal solution to the primal LP.

3. (14 points) Consider the following LP

min 5x+y+2z x,y,z

s.t. x + 2y + z = −5 2x − y + 3z ≥ 1 x, y, z ≥ 0

(a) (6 points) Perform phase 1 of the Simplex method.

(b) (8 points) Take the dual and use your conclusion from the previous part to deduce the solution to the dual problem.

4. (8 points) Suppose we are solving a maximization LP with 3 variables and 3 constraints using the Simplex method, and arrive at the following tableau:

−81w1 x1 −58w1 x 2 − x 3 14 w 1

−x3 2w1−w2

Is the solution to this LP unique? If so, provide a justification for uniqueness and the optimal values of the

variables, including the slack variables. Otherwise, please explain why there could be multiple optimal solutions. 1

−83w3 = z 18w3 = 5 − 41 w 3 = 4 =0

5. (10 points) In class, you have seen a compact formulation of the shortest path problem in a directed graph. State a compact formulation of the shortest path with the following extra requirements:

(a) (5 points) Given l ∈ V, where V = {0,...,n} is the set of nodes in the network, the shortest path from node 0 to node n must go through node l.

(b) (5 points) Given M ⊂ A, where A is the set of arcs in the network, at most l arcs from M are a part of the path.

6. (14 points) Consider the following branch-and-bound tree for an Integer Programming problem in maximization form.

(a) (8 points) Assuming that the coefficients in the objective function and constraints are all integer, say for each of the leaf nodes what is the status and what the algorithm is supposed to do.

(b) (6 points) Assuming that the left (resp. right) branch is always in ≤ (resp. ≥) form, reconstruct the branching decisions of the tree.

7. (12 points) Consider the following Min-cost Flow network. Assume all edges have cost 0 and infinite capacity unless otherwise indicated, and numbers on the nodes indicate the supply.

(a) (4 points) Does the problem have a feasible solution?

(b) (2 points) Is there a tipping point c for the capacity of the edge from the top right 0 transshipment node to the top demand node (i.e., the instance is feasible with all the other capacities remaining the same if and only if the capacity of the edge ≥ c).

(c) (6 points) Answer the above questions for the following network as well but with the edge from the top supply node to the top left 0 transshipment node.

  Page 2

 8. (10 points) Consider the Uncapacitated Facility Location problem. (a) (5 points) Can one replace constraints

with constraints

yij ≤xj i∈D, j∈F Xyij ≤|D|xj j∈F

i∈D

and still have a valid model?

(b) (5 points) What is the effect of changing the definition of variables y’s from

to

??

yij ∈{0,1}, i∈D,j∈F yij ≥0integer, i∈D,j∈F

9. (13 points) Assume that in a stochastic optimization problem one has a single event that realizes in three different ways: case (a) with probability 20%, case (b) with probability 45% and case (c) with probability 35%. In addition, assume that if the event realizes with case (a), another event will have to be considered realizing in two different ways: (a.1) with probability 15% and (a.2) with probability 85%.

(a) (9 points) Draw the scenario tree associated with those probabilities.

(b) (4 points) Which is the probability that the scenario associated with case (a.2) realizes?

Page 3