IE507-Lab3 Solved

Instructions: (Please read the instructions carefully and follow them!)

In this session, we will investigate how to query different solvers in Pyomo and check the error (or warning) messages. We will see how to modify various aspects of the optimization problem depending on the solver status or according to emerging needs.

Pyomo provides some options to reset sense of the optimization problem (to max or min), reset upper and lower bounds of variables, add new variables, add/deactivate constraints and add/deactivate objective functions.

We will also practice modeling optimization problems with integer variables in this lab. Integer optimization problems are those where some or all variables can take only integer values in the solution. When all the constraints and the objective function in a problem are linear, we call it an Integer Linear Program or Mixed-Integer Linear Program (MILP).

MILPs are used to model many problems, and have found even more applications than linear optimization. Though MILPs differ from LPs only in terms of integrality constraints on the variables, MILPs are in fact much harder to solve than LPs.

Please follow the instructions given below:

•    Please use different notebooks for solving different problems.

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

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

•    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 2 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 Lab3 and copy your .ipynb files to the folder. Then zip the folder to create YOURROLLNUMBER IE507 Lab3.zip. Then upload only the .zip file to Moodle.

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

Exercise 1: Resolving LP using different options [15 marks] Consider the optimization problem denoted (OP):

min x1− x2 + x3

s.t. x1 ≥ 1,x2 ≥ 1,x3 ≥ 2,

2x1− x2 + 2x3 ≤ 4,

2x1− 3x2 + x3 ≤−5, −x1 + x2− 2x3 ≤−1.

1.    Solve the problem (OP) using cbc solver and glpk solver. Check the solver status and solver termination criterion for both solvers. Are they meaningful? Explain possible reasons for the solver status and solver termination criterion message.

2.    In order to address the issue faced during solving problem (OP), you decide to use only cbc solver and intend to perform the following resolution steps independent of each other and check the result of the solver in each case.

(a)    Change the optimization problem to a maximization problem and re-solve.

(b)    Add an upper bound on x2 as x2 ≤ 5 and re-solve.

(c)     Add a new constraint x2− x3 ≤ 6 and re-solve.

(d)    Deactivate the objective of problem (OP) and construct a new objective of the form minx1 + x2 + x3 and deactivate the constraint 2x1− 3x2 + x3 ≤−5 and add a different constraint x1 + x2 ≥ 25.

In each of the above resolution steps (a)-(d), explain the solver termination condition and solver status message and provide possible reasons for the messages obtained. Whenever you get optimal solutions, print the values of the objective function value, values of decision variables and print if the constraints are active or not.

Exercise 2: A first example of MILP 

As a student in IITB, you are involved in selecting courses for completing your course requirements. You also want to make sure that the courses you select are interesting to you. Suppose that there are ten courses C1, C2, ..., C10 being offered this semester. By completing each course you get the following credits:

Course
Credit
C0
2
C1
3
C2
5
C3
4
C4
6
C5
6
C6
8
C7
8
C8
6
C9
4
C10
6
You must gather at least 26 credits this semester. However your course selection depends on the following constraints:

•    You must register for at least 5 courses and can register for up to a maximum of 9 courses this semester.

•    Courses C5 and C7 run during the same slots.

•    Courses C3 and C9 run during the same slots.

•    If you register for course C7 you cannot register for course C2.

•    If you register for courses C10 you must register for course C1.

•    Among the courses C0, C1, you must register for at least one course and can only register for at most one course.

•    Among the courses C2, C4, you can only register for at most one course.

•    Among the courses C8, C10, you can only register for at most one course.

1.    [R] Write a mathematical model so that you can maximize your credits to be accumulated this semester. Explain how to design the model variables and indicate which variables are integers. (We usually replace the notation x ∈ R by x ∈ Z to denote that variable x is integer).

2.    Use pyomo to construct your model.

3.    [R] Solver your MILP using cbc solver and report the optimal values of the variables and the objective function value.

4.    [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 optimal values of the variables and the objective function value.

5.    [R] Can the solution of the MILP be obtained by merely rounding the solution of the LP?

Why or why not?

6.    [R] Suppose a new course C11 with 9 credits is introduced, but the course timing for C11 overlaps with the course timings of C7, C8, how will you change your model to include this new constraint?

7.    [R] Solve the modified MILP and report the optimal values of the variables and objective function value.

8.    [R] Solve the modified MILP by removing the integer constraints on the variables and check if the solution of the modified MILP can be obtained by merely rounding the solution of the corresponding modified LP? Explain.