IE507-Lab6 Solved

Instructions:

We will practice modeling non-linear optimization problems as linear programs in this lab.

We will continue to model problems by loading information from files in this lab.

Please follow the instructions given below:

•    Please use different notebooks for solving different problems.

•    The notebook name for Exercise 1 should be YOURROLLNUMBER IE507 Lab6  Ex1.ipynb.

•    Similarly, the notebook name for Exercise 2 should be YOURROLLNUMBER IE507 Lab6  Ex2.ipynb, etc.

•    Please post your doubts in MS Teams or Moodle so that TAs can clarify.

For more details on pyomo, please consult https://pyomo.readthedocs.io/en/stable/index. html.

There are only 3 exercises in this lab. Try to solve all problems on your own. If you have difficulties, ask the Instructors or TAs.

Only the questions marked [R] need to be answered in the notebook. You can either print the answers using print command in your code or you can write the text in a separate text tab. To add text in your notebook, click +Text. Some questions require you to provide proper explanations; for such questions, write proper explanations in a text tab.

After completing this lab’s exercises, click File → Download .ipynb and save your files to your local laptop/desktop. Create a folder with name YOURROLLNUMBER  IE507 Lab5 and copy your .ipynb files to the folder. Also copy the .csv files to the folder. Some questions require the appropriate files to be included in folder. Please include all related files required to execute your code in the folder. Then zip the folder to create YOURROLLNUMBER IE507 Lab5.zip. Then upload only the .zip file to Moodle.

Exercise 1: Objective function with absolute value function

Consider the optimization problem (OP) considered in the practice code and its equivalent linear program problems (OP1) and (OP2).

1.       Use cbc solver to solve optimization problem (OP1).

2.       [R] Report the solver status and solver termination condition. Does the solver yield an optimal solution? If not, illustrate the reason for non-optimality and devise appropriate remedies so that you get optimal solution values. Explain the remedy measures you used.

3.       [R] If the solver results in optimal solution, report the optimal objective function value, values of the decision variables xi and the new variables ui and the constraint activities at the optimal solution. List your observations about the optimal values of original decision variables xi and the new decision variables ui.

4.       Now consider the optimization problem (OP2). Create a file containing the coefficients of objective function and constraints in problem (OP2). Name the file as lab6 practice coef OP2.txt

5.       Copy the file to colab environment.

6.       Use numpy to load the .txt file contents.

7.       Write a pyomo model to solve problem (OP2).

8.       Use cbc solver to solve the model for optimization problem (OP2).

9.       [R] Report the solver status and solver termination condition. Does the solver yield an optimal solution? If not, illustrate the reasons for non-optimality and devise appropriate remedies so that you get optimal solution values. Explain the remedy measures you used.

10.   [R] If the solver results in optimal solution, report the optimal objective function value, values of the decision variables ai and bi, and the constraint activities at the optimal solution.

11.   [R] Write code to print the original variables xi from ai and bi and print the values of xi.

12.   [R] Compare the xi values obtained from solving problem (OP1) and problem (OP2). Comment on your observations.

Exercise 2: An optimization problem with non-linear absolute value function in the constraints [20 Marks]

Recall the advertisement problem considered in practice session of Lab 4. We considered the optimization problem:

max 35x1 + 57x2 + 48x3 + 20x4 + 15x5,

s.t. x1 + x2 + x3 ≤ 75, x3 + x4 + x5 ≤ 100, x1 + x2 ≥ 10,

30000x1 + 95000x2 + 10000x3 + 5000x4 + 4000x5 ≤ 1500000, 100000x1 + 500000x2 + 200000x3 + 45000x4 + 25000x5 ≥ 900000,

                                                                                                               xi ≥ 0,          i ∈{1,2,3,4,5}.            (OPT-ADV)

where x1,x2,x3,x4,x5 denote the number of different types of media slots (assumed to be nonnegative integers) to be used for advertisement, where x1 corresponds to website, x2 corresponds to TV, x3 corresponds to daily newspaper, x4 corresponds to weekly magazine and x5 corresponds to monthly magazine.

1.    [R] Let z1 denote the total number of media slots used for website and TV and let z2 denote the total number of media slots used for other mediums. We wish to introduce a new constraint into problem (OPT-ADV) where the absolute value of difference between z1 and z2 cannot exceed 18. Write the formulation obtained by introducing this new constraint into the optimization problem (OPT-ADV). Note that your formulation should not contain z1 and z2 and should be in terms of the original decision variables x1,...,x5. Is the resultant formulation a linear program? Why or why not? Explain with appropriate reasons.

2.    [R] If the resultant optimization problem is not a linear program, use Approach 1 and Approach 2 discussed in Lab 6 practice session to convert it to respective linear programs and write the new formulations.

3.    Use the code used in Lab 4 practice session and modify it so that you can solve the new linear programs resulting from Approach 1 and Approach 2.

4.    [R] Solve the respective linear programs obtained from Approach 1 and Approach 2 and report the solver status and termination conditions. Are you getting optimal solutions in each case? If not, illustrate the reasons for non-optimality and devise appropriate remedies so that you get optimal solution values. Explain the remedy measures you used.

5.    [R] For each of the respective linear programs obtained from Approach 1 and Approach 2, report the optimal objective function values, optimal values of the original decision variables and the new decision variables and the constraint activities in each case.

6.    [R] Report your observations on the optimal values of the original decision variables obtained using Approach 1 and Approach 2.

7.    [R] Suppose we wish to introduce a different new constraint to the optimization problem (OPT-ADV). Let z3 denote the total number of media slots allotted for weekly and monthly magazines. Suppose we want the absolute value of difference between z3 and x3 (recall x3 corresponds to the number of media slots used for newspapers) must be at least 4. Write the formulation obtained by introducing this new constraint into the optimization problem (OPT-ADV). Note that your formulation should not contain z3 and should be in terms of the original decision variables x1,...,x5. Is the resultant formulation a linear program? Why or why not? Explain with appropriate reasons. Illustrate how you will convert this new formulation into a linear program.

Exercise 3: Fitting data using a linear model. (Adapted from Bradley, Hax, and Magnanti, Addison-Wesley, 1977) [15 Marks]

The selling prices of a number of warehouses in Powai overlooking the lake are given in the following table, along with the size of the lot and its elevation.

 

                                  Warehouse     Selling price       Lot size (sq. ft.)       Elevation (feet)

 

 

Table 1: Selling prices for different lot sizes and elevations

You have been asked by Marol Warehousing Company to construct a model to forecast the selling prices of other warehouses in Powai from their lot sizes and elevations. The company feels that a linear model of the form P = b0+b1L+b2E would be reasonably accurate and easy to use. Here b1 and b2 would indicate how the price varies with lot size and elevation, respectively, while b0 would reflect a base price for this section of the city. You would like to select the best linear model in some sense. If you knew the three parameters b0,b1 and b2, the six observations in the table would each provide a forecast of the selling price as follows:

                                                             Pei = b0 + b1Li + b2Ei                 i = 1,2,...,6.

However, since b0,b1 and b2 cannot, in general, be chosen so that the actual prices Pi are exactly equal to the forecast prices Pei for all observations, you would like to minimize the absolute value of the residuals Ri = Pi − Pei.

In this lab, we will solve this problem for 6 data points in Table 1.

1.    [R] Write a general optimization problem using the actual objective provided in the description. You may assume that b0 ≥ 0 and b1,b2 do not have bounds on them. Is the optimization problem linear? Explain.

2.    Use Approach 1 and Approch 2 described in Lab 6 practice to convert the optimization problem into respective linear programs.

3.    Create an appropriate .csv file from Table 1, which you can use during the construction of the objective function and the constraints for both approaches.

4.    Construct pyomo models for the respective linear programs resulting from Approach 1 and Approach 2.

5.    [R] Solve the respective linear programs obtained from Approach 1 and Approach 2 using cbc solver, report the solver status, solver termination conditions, optimal solution values for the original and new decision variables, and the optimal sum of residuals. Comment on your observations.