Problem 1. (10 Points)

a) Let A ∈ Rm ×n be a matrix and consider the polyhedron P = {x ∈ Rn  : Ax ≥ 0, x ≥ 0}.  Suppose for every x ∈ P we have x1  = 0.  Prove that there exists y ∈ Rm such that AT y ≤ 0, y ≥ 0 and y · A1  < 0.

b) Consider the following linear program in standard form

minimize   c · x

subject to    Ax = b

x ≥ 0

Let x∗ be an optimal basic feasible solution to this problem induced by basis B. Assume that B is non-degenerate. Prove that the dual of this linear program has a unique optimal solution.

c) Let P = {p ∈ Rn  : Ax ≤ b} and Q = {q ∈ Rn  :A(ˆ)x ≤ b(ˆ)} such that P ∩ Q = ∅.

Use LP duality to prove that there exists c ∈ Rn  such that (p − q) · c  > 0 for every p ∈ P and q ∈ Q.

Problem 2. (10 Points)

a) Suppose we are playing a two-player zero-sum game, such that no two out- comes in the payoff matrix P have the same value. I claim the number of pure equilibria to this game is always either 0 or 1.  Am I correct?  Provide a short proof or a counterexample.

b) Suppose we are playing a simplified version of the board game Battleship. You must choose two adjacent squares on a 2 × 3 grid on which to hide your battleship. I then choose a single square to target with my attack. If I hit your battleship it sinks and I win the game.  If I miss you win the game.  What is the mixed equilibrium for this game and (assuming we both follow our equilibrium strategies) what is the probability that I win?

c) Suppose we are playing a two-player zero-sum game with payoff matrix P ∈ Rm ×n  such that for a particular k  ∈ [n] we have  pi,j   ≥ pi,k  for all  i  ∈ [m], j ∈ [n].  I claim that column k can be removed from P without changing the value of the game. Am I correct? Provide a short proof or a counterexample.

Problem 3. (10 Points) I have n final-year students {s1, s2, . . . , sn} in need of cap-  stone projects and m available projects {p1, p2 . . . , pm }. Every student picks k projects they are interested in and ranks them from 1 tok.  If a student is assigned to their  jth ranked project we say the student has unhappiness j.  Every student must be as-  signed to exactly one project. We may assign multiple students to the same project,  but no project may have more than 3 students assigned to it.  Students may not be  assigned to projects that are not in their k preferred projects. Your task is to assign  students to projects in a way that minimizes average unhappiness.

a) Write down an integer linear program that models this problem. b) Write down the linear relaxation of that integer program.

c) Show that the linear relaxation will always have an integral optimal solution. Show this without applying unimodularity.

d) Hence describe how this problem can be solved using linear programming in polynomial time.

Problem 4. (10 Points) We are interested in the Square Traveling Salesman Problem. In this problem we are given a set P ⊂ R2  of cities. The cost of traveling between cities p and q ∈ P is the square of the euclidean between them,i.e.  ∥p − q∥2(2).  The Square Traveling Salesman Problem is to find a tour that visits every city in P and returns to where it started, while minimizing the total cost of traveling between the cities.

Let Xn  be a set of n points chosen independently and uniformly at random from the unit square [0, 1]2 .  Let f(Xn ) be the cost of an optimal Square Traveling Salesman Tour on Xn .  We are interested in understanding the asymptotic (in n) behaviour of E(f(Xn )). This seems difficult to understand theoretically, so we will investigate it empirically instead.

a) Write down the integer linear programs for the Traveling Salesman Problem and the Square Traveling Salesman Problem.  Does it matter that ∥p − q∥2(2) is not a linear function?

b) Sample a random set of points Xn  for values of n = {2, 4, 8, 16, . . .} and com- putef(Xn ) using gurobi.  Continue increasing n by a powers of 2 until the solver takes more than a few seconds to return.

c) For each value of n used in the previous step sample 10 additional point sets Xn, compute f(Xn ) for each point set and calculate the average value off(Xn ) for each n.

d) Plot this estimation of E(f(Xn )) against n (Include the plots in your assignment).

e) Therefore propose a hypothesis function h : Z≥0  → R such that E(f(Xn )) = Θ(h(n)) based on your experimental data.