In this assignment, you will solve the online allocation problem that you have seen in class by using duality. The problem is the following:

There are m resources, x1 , , xm with fixed capacities b1, , bm

Demand requests arrive sequentially, noted j = 1...N, with requirements ai, i=1m and profit p

We want to make accept/reject decisions without knowing future demands

We have the historical data of N demands in the file demand.csv:

Part A:

In this question, you will formulate the problem as a linear program. To do so, you will transform the LP to standard form:

max cTx

Ax <= b

x >= 0

while cT represents the profit of accepting each demand, A represents the number of required resources, and b represents the upper bound limit for each resources.

You will take m=4, N=100, b0=125, b1=130, b2=118, b3=137 and use the data in the file data_online_allocation.csv which simulates the demand for N=100. Return A as a matrix, b as a list, and c as a list.

Note: When you construct the matrix A (lists within list), the first 4 rows will correspond to the capacity constraints and the following 100 rows will correspond to the upper bound of xi for i=1...100

Part B:

In this question, you will use the standard form that you have set up in the previous question. Write the dual and solve it using Gurobi. As a reminder, the dual is:

min bTy

ATy >= c

y >= 0

Return the optimal objective value, and the optimal values of the variables in one list.

Note: The list of the optimal values of the variables should contain the dual of the capacity constraints in the first 4 position

Part C:

Use the shadow prices you fund in the previous questions to create a static policy to make the accept/reject decisions. Apply that policy to the products in the file "new_data.csv" and return the list of the products you reject (this list is called reject_list).

The list should be of the form: [2,7,38] (i.e. it should contain the index of the product, which goes from 1 to 100)

(Hint) Accept if:

Pj - sum(lambdai * aij , i=1..m) >= 0

where lambdai are the values you calculated when solving the dual in question 2.

The demand forcast file is as follows:

a1,a2,a3,a4,p 5,1,3,1,3 4,2,3,2,16 3,1,2,1,8 0,1,2,0,9 3,2,3,3,16 4,1,2,3,13 2,0,1,1,5 3,1,3,3,8 4,3,0,2,9 3,1,1,1,5 2,1,1,2,3 1,3,2,1,6 0,1,2,0,3 2,2,2,1,6 6,1,0,2,11 6,2,2,2,4 2,3,2,2,12 0,2,2,2,13 4,1,3,2,3 1,1,1,2,11 5,1,2,2,1 1,1,0,1,13 3,2,3,1,4 2,1,0,2,7 2,1,1,1,6 3,2,2,1,13 1,0,2,1,6 0,1,0,1,4 2,3,1,2,16 1,2,1,3,13 2,1,1,0,4 5,2,2,2,13 0,3,2,1,7 5,1,0,3,14 4,2,2,0,14 0,1,0,3,12 4,2,1,0,15 0,2,2,0,7 3,0,0,1,2 1,3,3,2,4 4,2,2,1,5 5,1,0,0,3 2,2,2,3,11 6,1,0,1,4 3,3,2,2,4 5,2,0,3,9 6,3,2,1,6 2,2,3,3,7 1,0,2,1,11 3,1,2,1,13 6,0,1,3,9 5,2,0,3,11 5,1,3,1,5 3,2,0,3,12 2,1,3,2,5 5,2,1,1,9 5,2,1,0,6 1,1,1,1,1 6,2,2,2,12 3,3,3,1,7 6,0,0,2,7 1,2,2,3,3 4,0,1,3,8 5,0,0,2,4 5,3,1,2,1 4,2,1,2,5 1,1,0,2,8 0,2,1,0,9 1,2,2,0,3 3,0,3,2,12 4,2,1,3,3 4,2,2,2,9 5,1,2,1,7 3,2,1,0,16 2,2,2,1,15 1,0,2,2,5 4,2,1,2,5 0,2,2,0,15 2,1,3,1,10 2,3,1,3,4 5,2,2,3,7 2,1,3,1,10 3,2,0,2,1 1,1,1,0,10 3,1,0,2,4 5,3,1,3,14 4,0,3,1,8 4,3,1,0,10 6,2,0,2,9 0,1,0,3,9 2,2,2,1,6 1,0,0,1,10 2,0,0,0,3 0,3,1,1,10 2,1,2,1,11 5,2,0,1,2 3,1,3,2,14 4,1,2,3,12 5,2,3,1,2 1,2,1,1,4

There is also a file new_data as follows:

a1,a2,a3,a4,p 1,2,2,1,10 0,2,3,2,5 0,1,1,2,15 0,0,3,2,2 0,3,2,3,12 2,1,3,2,7 2,2,1,1,4 2,1,3,2,15 1,1,2,1,9 1,0,2,1,9 0,1,2,3,10 3,2,0,3,4 3,2,1,0,1 1,1,2,1,15 0,2,2,1,2 1,2,2,1,2 2,1,2,1,7 1,0,1,2,15 1,0,3,1,9 1,3,2,1,15 2,2,3,3,5 2,3,1,2,2 3,3,3,0,13 3,1,2,3,12 0,1,3,1,9 0,2,3,3,8 2,1,2,3,11 3,2,1,2,13 0,2,1,2,10 1,2,2,2,5 2,0,1,1,11 2,0,3,2,15 1,0,1,0,10 1,3,2,1,7 3,2,1,1,14 2,3,2,0,1 1,1,3,0,14 1,2,3,1,1 3,2,1,2,13 1,2,2,2,7 1,3,2,0,1 2,3,1,1,7 1,0,1,0,1 3,3,3,2,7 1,3,1,1,14 0,2,0,2,11 2,1,0,2,10 2,3,3,3,9 1,1,1,0,14 2,0,2,0,1 2,1,0,3,15 1,1,1,1,16 1,1,1,1,6 1,1,0,2,8 0,3,3,1,6 0,2,3,3,4 0,2,1,2,11 2,2,2,1,7 1,1,2,2,14 3,3,2,2,15 2,2,1,1,7 2,2,1,3,4 2,0,2,1,3 3,2,1,2,13 0,0,1,1,12 1,1,1,1,15 1,1,1,1,11 2,2,1,2,13 2,1,2,3,2 3,0,1,1,11 3,1,2,1,13 2,2,1,2,12 1,2,0,1,4 2,1,1,1,4 2,0,1,1,7 1,2,1,0,9 0,2,1,2,11 1,1,1,2,14 2,1,2,1,14 1,2,1,2,12 2,1,1,2,14 1,2,1,3,7 0,3,1,3,11 2,0,2,1,3 0,2,0,1,7 0,2,1,3,1 0,2,2,2,11 1,1,1,2,4 1,2,1,1,3 1,1,0,0,11 3,1,2,1,12 2,0,1,1,13 0,3,3,2,9 2,1,2,2,12 3,2,1,1,12 1,2,3,0,12 3,0,3,2,4 1,2,1,3,11 3,0,3,0,14 5,1,2,2,13