Introduction to Optimization Recitation 9

Introduction to Optimization Problem 1: Gomory Cuts Consider the following integer program: max − 2 x + 4 y 4x + 6y ≤ 24 − x + y ≤1 s.t. x, y ≥ 0, integer The initial and final tableaux (after slack variables are added) are: z 1 0 0 x 2 4 -1 y -4 6 1 s1 0 1 0 s2 0 0 1 RHS 0 24 1 z 1 0 0 x 0 1 0 y 0 0 1 s1 0.2 0.1 0.1 s2 2.8 -0.6 0.4 RHS 7.6 1.8 2.8 and a) Plot the feasible region of the IP and its LP relaxation. b) Note that the optimal solution to the LP relaxation is fractional. Construct a Gomory cut that makes the current optimal solution infeasible, but doesn’t affect any integer solutions. c) What would the new solution to the LP relaxation be (with the cut added)? d) Did adding the cut improve the bound given by the LP relaxation? Problem 2: Integer Programming The Transylvania Olympic Gymnastics Team consists of six people. For their upcoming competition, Transylvania must choose three people to enter both the balance beam and floor exercises. They may also enter one additional person in each event, who competes in only that event. The score that an individual gymnast can attain in each event is shown in the table below. Gymnast 1 2 3 4 5 6 Balance Beam 8.8 9.4 9.2 7.5 8.7 9.1 Floor Exercise 7.9 8.3 8.5 8.7 8.1 8.6 a) Formulate an integer program to maximize the total score obtained by the Transylvanian gymnasts. b) Gymnasts 2 and 4 use the same music for their floor exercise, so they do not wish to both perform in that event. How would you model this additional constraint? c) Gymnasts 5 and 6 are sisters, and they like to do everything together. How do you model the constraint that if one of them is picked to participate in the competition, then the other one should participate as well? Problem 3. Network Formulation Each year, IBM produces as many as 400 computers in Boston and 300 computers in Raleigh. Los Angeles customers must receive 400 computers, and Austin customers must receive 300 computers. Producing a computer costs $800 in Boston and $900 in Raleigh. Computers are transported by plane and may be sent either directly or through Chicago. The cost of sending a computer between pairs of cities is shown in the following table: From Boston Raleigh Chicago Chicago 80 100 ---- To Austin 220 140 40 Los Angeles 280 170 50 a) Show how the problem of minimizing the total (production + distribution) cost of IBM’s annual demand can be expressed as a minimum cost network flow problem. What do the nodes represent, and what do the arcs represent? b) How would you modify the part a) formulation if at most 200 units could be shipped through Chicago? (Hint: add an additional node and arc to the network.) Problem 4. Game Theory Two players are playing the game ‘rock, paper, scissors’. They both shout out a word at the same time and give a corresponding hand signal. If both players say the same word, then the game is a draw. Otherwise, one player wins $1 from the other according to the following rules: scissors defeats (cuts) paper, paper defeats (covers) rock, and rock defeats (breaks) scissors. a) Model this game as a two-person, zero sum game. Give the corresponding payoff matrix. b) Write the LP for finding the row player’s optimal strategy. c) Write the LP for finding the column player’s optimal strategy. d) What is the relationship between the optimal payoff to the row player and the optimal payoff to the column player?