In this assignment, you will solve the online allocation problem that you have seen in class by using duality using Python and Gurobi. 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

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