IE507-Lab4 Solved

Instructions:

We will practice modeling optimization problems by loading information from files in this lab. We will also continue modeling problems with integer variables.

To load directly from a .txt file containing numbers, we will use the numpy.loadtxt() construct. To know more on the numpy methods to load from files, please check https://numpy.org/doc/ stable/reference/routines.io.html.

To load directly from a file with comma separated values (.csv file), we will use pandas library. The construct pandas.read csv helps to read contents from a .csv file. Please check https:

//pandas.pydata.org/pandas-docs/stable/getting_started/index.html to know more about pandas library.

Please follow the instructions given below:

•    Please use different notebooks for solving different problems.

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

•    Similarly, the notebook name for Exercise 2 should be YOURROLLNUMBER IE507 Lab4  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 Lab4 and copy your .ipynb files to the folder. Then zip the folder to create YOURROLLNUMBER IE507 Lab4.zip. Then upload only the .zip file to Moodle.

The deadline for today’s lab submission is tomorrow, 10th September 2020, 11 59 PM Indian Standard Time (IST).

Exercise 1: Loading values from a file [6 marks] Consider the following optimization problem:

max−0.5x1− 1.25x2− 5x3 + 3x4 + 10x5 + 25x6

s.t. 0.8x1− 1.3x2− x4 ≤ 12 x2− x3− x5 ≤ 0.6 x3− x6 ≤ 1.2 0.5x1 + 0.8x2 + 4x3 ≤ 45

0.9x1 + 1.5x2 ≤ 27,

                                                                                               xi ≥ 0 ∀i ∈{1,2,...,5}.                                                       (OP)

1.    Create a .txt file such that:

•    The coefficients of the objective function are present in the first line, separated by commas, and the last value represents the scalar (note that the scalar in the objective function is zero in problem (OP)).

•    The remaining lines contain the coefficients of the constraints (separated by commas) and the last value in each of the remaining lines represent the right-hand-sides of the constraints.

See the lab4 practicecoef.txt file used in practice.

2.    Name the file lab4 ex1 coef.txt

3.    Copy the file to colab environment.

4.    Use numpy.loadtxt to load lab4 ex1  coef.txt into an appropriate numpy array.

5.    Write code using pyomo to create the model for the optimization problem (OP) using the coefficients loaded from lab4 ex1 coef.txt file.

6.    Use cbc solver to solve the optimization problem (OP).

7.    [R] Print and explain the solver termination condition and solver status message and provide possible reasons for the messages obtained.

8.    If the solver does not give an optimal solution, try to devise a remedy and use it to get an optimal solution.

9.    [R] If you have devised a remedy, explain about it and then report the optimal objective function value, the values of variables and the constraint activities.

Exercise 2: Time taken in MILP. [10 marks] In this exercise we will compare the time taken to solve LP and MILP. Consider the integer optimization problem

 

X

                                                            s.t.              aijxj ≤ bi,

j=1
i = 1,...,m
(MILP)
xj ∈{0,1},

and its LP relaxation
j = 1...,n.
 
 

X

s.t.                aijxj ≤ bi,

j=1
i = 1,...,m
(LP)
0 ≤ xj ≤ 1,
j = 1...,n.
 
Specific data is available for this problem in Moodle in lab4  ex2 lp ip coef.txt file. It has n = 500 variables and m = 5 constraints. Note that the file is modeled similar to the lab4 practice coef.txt file used in practice session.

1.    Copy the lab4 ex2 lp  ip coef.txt file to colab environment.

2.     Use numpy.loadtxt to load lab4 ex2 lp ip coef.txt into an appropriate numpy array.

3.    [R] Create a pyomo model using the coefficients loaded from the file and solve the MILP using cbc solver. Report the optimal objective function value (Do not report the values of variables).

4.    [R] How much time does it take to solve the MILP? Suppose you have saved the results of opt cbc.solve to results, you can use results.solver.time to report time.

5.    [R] Solve the LP relaxation (LP obtained by removing integer restrictions on all variables) of the same problem using cbc solver. Report only the objective function values of the optimal solution. (You need not report the values of the variables.)

6.    [R] How much time does it take to solve the problem? Compare with the results obtained by solving the MILP.

7.    [R] Also report the statistics printed in Branch and Bound section of results for both MILP and LP.

Exercise 3: Another Exercise on LP Vs MILP [20 marks]

The simplest application of MILP is when the variables model discrete objects that can only take whole-number values (e.g. number of drones to manufacture). The Indian Air Force (IAF) has planned to purchase drones from the Hindustan Aeronautics Limited (HAL) for using them in surveillance activities and during crisis situations like floods, fires and earthquakes. The drones are expected to carry cameras and freight. Five different types of drones are available with HAL. Their carrying capacities, costs and parking space requirements are listed below:

Drone Model
Carrying Capacity (kgs)
Cost (in Crores of rupees)
Parking space (sq. m.)
SANKALP
15
4
3
KARTAV
10
3.5
3.25
SAAHAS
20
5
4
VIJAY
10
4
2.75
LAKSHYA
15
4.5
2.5
The IAF wants to have maximum possible carrying capacity. The budget of IAF is limited to 29 crores of rupees. In addition, parking space for drones is limited to 37 sq. m.

1.       Create a .csv file containing the data given in the table. Name the file as lab4 ex3.csv. Use simple and appropriate names for the headers.

2.       Copy the file to colab environment.

3.       Use pandas to load the .csv file contents.

4.       [R] Write a mathematical optimization problem to find the number of drones of each type that can be bought in order to maximize the goal. Mention which variables must be integers.

5.       Create a model using pyomo to solve your optimization problem. Use the loaded contents of .csv file to create your model. Use cbc solver to solve your optimization problem. In your code, remember to specify which variables are integers.

6.       [R] Report the optimal objective function value and the solution.

7.       [R] Let us now compare it to a linear program. Suppose we remove the restrictions that the variables in the above problem are integers. Solve this modified problem and report the solution and the objective value.

8.       [R] Can the solution of the MILP be obtained by merely rounding the solution of the LP? Why or why not?

9.       [R] Suppose now we are interested in finding how the solution changes when the right-handsides in our constraints change. Suppose the limit on budget is increased to 41 units and the parking space is increased to 47 units, how will the new LP objective value change? How does the new MILP objective value change?

10.   [R] Now try decreasing limit on budget from 41 units to 39, 37, 35 and 33 units. Correspondingly, increase the parking space to 49, 51, 53 and 55 units. Solve the LP and MILP for each of these four possiblities and comment on the pattern seen in objective values of the LP and MILP.