Consider the following integer-linear program which is used to decide which warehouses to open from a set of n potential warehouses, and how to assign m retail stores to the opened warehouses (for receiving supplies). Note that each retail store must be assigned to exactly one warehouse. Each warehouse can serve all the retail stores. Associated with each assignment is a transportation costcij,i=1,,n,j=1,,m, and associated with opening each warehouse is a fixed cost fi,i=1,,n. We seek to minimize the total cost. This is known as a location-allocation model. Let xij={1,0,ifstorejisassignedtowarehousei,i=1,,n,j=1,,m,o/w, 1 ISE-321 HW-3 and yi={1,0,ifwarehouseiisopened,o/w Then, the location-allocation model is: mins.t.z=i=1nj=1mcijxij+i=1nfiyii=1nxij=1,j=1mxijmyixij{0,1},i=1,,m, Assume that n=4,m=5, and that the fixed cost for opening a warehouse is $20,000 for each of four warehouses. The transportation costs for all pairs of warehouses and stores (in thousands) are provided in the table below: Questions: 1. For the solution [1,0,0,1] which represents that warehouses 1 and 4 are open, compute the total cost, z(x,y) and describe how you did so. Note that the notation for solutions that we will use uses a 1 to indicate that the corresponding warehouse is open and 0 otherwise. 2. Run Tabu Search for five iterations with tenure period =2, and starting with the solution [1,0,0,1]. A neighborhood here is defined as a solution in which the status of only one warehouse is flipped, i.e., you can flip one warehouse from being open to being closed or vice versa to generate a neighbor (except if that warehouse is on the Tabu list). If a warehouse is flipped from open to closed or vice versa, that warehouse (not the entire solution) should then go on the Tabu list. Use random-walk selection for neighbors. For this part, use the random numbers from seed (1,1), and use them in this order! Show detailed work for every iteration, then at the end of the algorithm, report the best solution found. 3. Run Simulated Annealing for five iterations. Set T0:=0.25F([1,0,0,1]T) and ri=0.25,i 1 (i.e., Tk:=0.25Tk1k1 ), and t=2 (i.e., reduce the temperature after every two accepts) starting from [1,0,0,1]. Use the same neighborhood definition as above, and greedy selection for the neighbors. Show detailed work for every iteration, then at the end of the algorithm, report the best solution found. For this part, use the random numbers from seed (1,1) for accept/reject decisions (use them in this order!). Use the first number in this list for the first comparison you have with eTk (regardless of what iteration it happens to be), i.e., if the first comparison you do is in iteration 5, then you should use the first random number in this list. Instructions for Obtaining Random Numbers For each problem (1&2) or its part where random numbers are needed, obtain them from the consecutive random digits from Random Number Table as follows. Start from a seed location. Assume for this HW the seed location is first column \& first row of the table (i.e., seed at (1,1) ). Now read the five-digits of from the seed location and form a random numbers by placing a decimal point in front. From seed (1,1) the first random number is 0.13962 , and the second random number is 0.70992. Once you reach the end of the first row, start from the first column of the next row. Always restart the generation of random numbers for each new problem (or any sub-problem). For this HW the seed is (1,1). If any random number that you use results in infeasibility, then discard it and move to the next random number. An example for Problem-1 is given below. Extended Neighbors For generating an extended neighbor, you need two random variables R1 and R2, such that 0 R11 and 0R21. Use first random variable (R1) to identify the position or variable to update from the current solution. Use second random variable (R2) to get the value of the selected element. To select the variable or position to update, use the following formula: position=1+R1M where M is the total number of variables, U is the floor function. If the position is infeasible, then repeat the above position calculation with the next random number until we get a feasible position. To get the value of the selected position, use the following formula. value=oldvalue+(R20.5)(UL) where U and L are upper and lower bounds on the selected variable. If the value is infeasible, then repeat the above value calculation with the next random number until we get a feasible value. Example: Say the seed is at (1,1) and let [9,4,1,1,3,1]T be the current solution. Since seed is at (1,1),R1=0.1396. Now, based on the position formula, we get position =1+0.13966=1+0.8376=1+0=1. Therefore, first variable is updated, i.e., the extended neighbor will be [,4,1,1,3,1]T of this form. Now the value for the position is obtained by using the next random number (i.e., R2=0.70992 ). So, the value =9+ (0.709920.5)(90)=1+1.88928=9+1=10. The value is infeasible for Problem- 1 , so we repeat with the next random number, which is R2=0.65172. Now using the formula, we get value =10 (again infeasible). Now, the next in line random number, R2=0.28053, will be used. This will result in value =9+(0.280530.5)(90)= 1+1.97523=92=7 Thus, the randomly selected extended neighbor will be [7,4,1,5,3,1]T