Graduate Artificial Intelligence 15-780Homework 4: Mathematical Programmin g\Out on March 1Due on March 22Homework 4 Graduate Artificial Intelligence 15-780Problem 1: Linear and Integer Programming (40 points)Consider the standard-form LP problemmin (or max)cTxSubject to:Ax = bx ≥ 0where x ∈ ℜnand A is an m × n matrix with n ≥ m.Recall that the simplex algorithm is an iterative algorithm to solve standard-form LPs. At each iteration, thesimplex algorithm has a candidate solution x has the property that at least n − m of its components are zero.Variables that are allowed to be non-zero are called basic variables, and variables that are forced to be zero arecalled non-basic variables. Without loss of generality, we can assume that x is ordered so that all the basic variablescome before all the non-basic variables. Letting xBbe the basic variables and xNbe the non-basic variables, wecan rewrite x asx = [xB; xN]Now, the matrix A is partitioned into two components: an invertible m × m matrix that we will call S−1; and C,the remaining m × (n − m) submatrix. We can rewrite A asA = [S−1C]Now consider the original equality constraint of the LPAx = bmultiply both sides by S to getS Ax = Sband since A = [S−1C], this is just[ImSC]x = Sbwhere Imis the m × m identity matrix. Now, rewriting x we have[ImSC][xB; xN] = SbThis system of equations is called the simplex tableau.• (5 points) Consider the following LP:max x + ySubject To2x + y ≤ 10x + 3y ≤ 12x, y ≥ 0What is the optimal solution of this LP? Sketch the feasible region.• (5 points) What is the dual of this LP?• (15 points) Now suppose we change the program to be an integer program by requiring that x and y both bePage 1 of 4Homework 4 Graduate Artificial Intelligence 15-780integers. Adding the slack variable s1and s2produces the standard form ILPmax x + ySubject To2x + y + s1= 10x + 3y + s2= 12x, y, s1, s2≥ 0 and integerConsider the LP relaxation of this ILP produced by dropping the constraint that the variables be integers.Create the simplex tableau for the basis {x, y}.• (15 points) Recall the Gomory cut algorithm described in class. Given a row from the simplex tableau, this al-gorithm produces a cut, a new constraint that both eliminates the current optimal solution in the LP withouteliminating any integer-feasible solutions.Run the Gomory cut algorithm by hand using the row from your simplex tableau corresponding to the basicvariable x. What is the resulting cut? Sketch the feasible region of the LP relaxation and the cut you produced.Does the new cut result in an integer-optimal solution?Problem 2: Stochastic Programming (60 points)In this problem, you will take the role of Scott Smith, owner of the East End Brewing Company in Homewood.Each week, you need to distribute kegs of beer to bars in various Pittsburgh neighborhoods. There are tenneighborhood bars that might demand kegs, and your goal is to minimize the total driving time on your route,where the truck starts and ends at your brewery in Homewood.The file times.txt is an 11-by-11 comma-separated value file showing the travel times between the variousneighborhoods in Pittsburgh, calculated using Google maps. The file shows the number of minutes it takes toget between the location listed on the row to the location listed on the column. Because of the vagaries of thePittsburgh road network, this is not a symmetric matrix (e.g., it takes 14 minutes to get from Troy Hill to Oaklandbut only 12 minutes to get from Oakland to Troy Hill).In this problem, whether or not a bar has demand for a keg is a random variable. In particular, we will explorethe case where each bar independently has demand drawn from a Bernoulli distribution with probability p, so thatthe demand diof bar i is given byP(di= 1)= p P(di= 0)= 1 − pLet a route be a set of nodes~r ≡ {r0,.. .,rk} such that r0= rk= HomewoodBrewery and all the neighborhoodswhere di= 1 appear exactly once in~r (neighborhoods where di= 0 may or may not appear in a route). Let Rdenote the set of all routes, and let t(a,b) denote the amount of time it takes to get from a to b.As stated, the problem is simply a traveling salesman problem, which you already know how to solve optimallyby using Integer Programming techniques. Now, we introduce one additional complication into the problem: atneighborhood r5, the demands for all the bars becomes known, and then the route can be re-optimized. This isnow a two-stage stochastic program with recourse, where the two stages are before and after the information isrevealed, and the recourse refers to the ability to change plans once the information is revealed. In particular,once the truck reaches r5you can re-optimize the route from that point to only visit the remaining bars that havedemand in an optimal way.To state your problem formally, you are looking to solvemin~r ∈R"5Xi=1t(ri−1,ri) + E~d³f (~d,~r )´#Page 2 of 4Homework 4 Graduate Artificial Intelligence 15-780where f (~d,~r ) is the amount of time to traverse the remaining bars and return the truck to HomewoodBrewery,given the demand vector~d and starting from r5.When 0 < p < 1, the optimal policy is given by the first five neighborhoods to visit, and then by a function thatmaps realizations of the demand vector to paths through space. However, since you would never want to traversea route that is not a minimal path through the remaining bars that have demand, for the purposes of the answersyou give in this problem the optimal policy for 0 < p < 1 can be characterized just by a path to the first 5 bars.You will solve this problem by using MIPs. Solvers such as CPLEX are available on linux.gp.cs.cmu.edu, andthere are also open-source solvers such as lpsolve you can run on your own machine. Probably the easiest wayto input a MIP into a solver is to use the CPLEX LP file format (and, in particular, writing a meta-program to writethe file for you). CPLEX LP files look like:Maximizeobj: x1 + 2 x2 + 3 x3 + x4Subject Toc1: - x1 + x2 + x3 + 10 x4 <= 20c2: x1 - 3 x2 + x3 <= 30c3: x2 - 3.5 x4 = 0Bounds0 <= x1 <= 402 <= x4 <= 3Generalx4EndThese files can be directly imported into your MIP solver. A guide to this file format can be found at goo.gl/RJWuw. Another, less-powerful approach is to use the functionality of the MATLAB optimization toolbox. As a lastresort, if you are unable to use CPLEX and have problems running lpsolve locally, please contact the TAs and wewill work out a way for you to run your LP