GitHub Repository: DataScienceUWL/DS775
Path: blob/main/Homework/Lesson 09 HW - IP/Homework_09.ipynb
⁸⁷¹ views

Kernel: Python 3 (system-wide)

Lesson 09 Homework - Integer Programming

When asking questions about homework in Piazza please use a tag in the subject line like HW1.3 to refer to Homework 1, Question 3. So the subject line might be HW1.3 question. Note there are no spaces in "HW1.3". This really helps keep Piazza easily searchable for everyone!

For full credit, all code in this notebook must be both executed in this notebook and copied to the Canvas quiz where indicated.

Textbook Problem 12.2-4

Reconsider the Wyndor Glass Co. problem presented in Sec. 3.1. Management now has decided that only one of the two new products should be produced, and the choice is to be made on the basis of maximizing profit. Introduce auxiliary binary variables to formulate an MIP model for this new version of the problem.

Hints for 1-5

This is really similar to choosing among three products in the Good Products example in the lesson.

Question 1 (Manually Graded) (2 points)

The original Wyndor model formulation using continuous variables is the following:

Maximize $Z = 3 d + 5 w$

subject to:

$\begin{array}{ccccc} d & & & \leq & 4 \\ & & 2w & \leq & 12 \\ 3d & + & 2w & \leq & 18 \end{array}$

where $d \geq 0$ , $w \geq 0$

Introduce auxiliary binary variables to formulate a mixed BIP model for this problem. Include a picture or LaTeX of the mathematical formulation.

Hint: The binary variables are only used in the constraints, so you will only need to provide the constraints and the notation to use integer decision variables.

Question 2 (Manually graded) (4 points)

Given the following abstract formulation for the continuous Wyndor problem, add the necessary auxiliary binary variables to solve the problem from Question 1.

Note: Starting code is included in the Jupyter notebook, but not in the quiz.

In [3]:

# Starting Code
from pyomo.environ import *

# abstract Wyndor
products = ['Doors', 'Windows']
plants = ['Plant1', 'Plant2', 'Plant3']
profit_rate = {'Doors': 3, 'Windows': 5}
hours_available = {'Plant1': 4, 'Plant2': 12, 'Plant3': 18}
hours_per_batch = {
    'Plant1': {
        'Doors': 1,
        'Windows': 0
    },
    'Plant2': {
        'Doors': 0,
        'Windows': 2
    },
    'Plant3': {
        'Doors': 3,
        'Windows': 2
    }
}



#Concrete Model
model = ConcreteModel()

#Decision Variables
model.weekly_prod = Var(products, domain=NonNegativeReals)
model.y = Var( products, domain = Boolean)

#Objective
model.profit = Objective(expr=sum(profit_rate[pr] * model.weekly_prod[pr]
                               for pr in products),
                      sense=maximize)

model.capacity = ConstraintList()
for pl in plants:
    model.capacity.add(
        sum(hours_per_batch[pl][pr] * model.weekly_prod[pr]
            for pr in products) <= hours_available[pl])

# Solve
solver = SolverFactory('glpk')
solver.solve(model)

# display solution (again, we've changed to f-strings)
print(f"Maximum Profit = ${1000*model.profit():,.2f}")
for j in products:
    print(f"Batches of {j} = {model.weekly_prod[j]():.1f}")

Out[3]:

Maximum Profit = $36,000.00
Batches of Doors = 2.0
Batches of Windows = 6.0

Question 3 (2 points)

What is the maximum profit? (Do not include dollar sign. Round to 2 digits.)

Question 4 (2 points)

How many doors will be produced?

Question 5 (2 points)

How many windows will be produced?

Textbook Problem 12.3-1

The Research and Development Division of the Progressive Company has been developing four possible new product lines. Management must now make a decision as to which of these four products actually will be produced and at what levels. Therefore, an operations research study has been requested to find the most profitable product mix.

A substantial cost is associated with beginning the production of any product, as given in the first row of the following table. Management’s objective is to find the product mix that maximizes the total profit (total net revenue minus start-up costs).

Let the continuous decision variables $x_1, x_2, x_3,$ and $x_4$ be the production levels of products 1, 2, 3, and 4, respectively. Management has imposed the following policy constraints on these variables:

No more than two of the products can be produced.
Either product 3 or 4 can be produced only if either product 1 or 2 is produced.
Either

5x_1 + 3x_2 + 6x_3 + 4x_4 \leq 6,000

\text{or}

4x_1 + 6x_2 + 3x_3 + 5x_4 \leq 6,000

Hints for 6-10

Constraint 1 is similar to the product choice constraint in Good Products.

Constraint 2 can be implemented with one or two inequalities invoving

y1, y2, y3, y4

.
One approach to understanding if your constraint is correct is to make a list
of the 16 possible combinations of 0's and 1's for

y1, y2, y3, y4

and identify all of the rows for which this constraint is satisfied,
then make sure your constraint is true for the same rows.

Contstaint 3 is similar to choosing between plants in the Good Products example.

Question 6 (Manually Graded) 4 points

Introduce auxiliary binary variables to formulate a mixed BIP model for this problem. Include a picture or LaTeX of the mathematical formulation in the next cell.

Hint: The objective function will need to use both real and binary decision variables.

Hint: It's easier to generalize your code if you use multiple binary variables as opposed to the 1-y construction.

Question 7 (Manually Graded) (4 points)

Use Pyomo to solve this model. Use an abstract formulation.

In [0]:

Question 8 (2 points)

What is the maximum profit? (Do not include dollar sign. Round to 2 digits.)

Question 9 (2 points)

Which products will be produced (select all that apply).

Product 1
Product 2
Product 3
Product 4

Question 10 (2 points)

At what rate will product 1 be produced per week?

Product 1 will be produced at 2000/week.
Product 1 will be produced at 200/week.
Product 1 will be not be produced.
Product 1 will be produced at 20000/week.

Textbook Problem 12.4-6

Note: This content not included in the Canvas Quiz

Speedy Delivery provides two-day delivery service of large parcels across the United States. Each morning at each collection center, the parcels that have arrived overnight are loaded onto several trucks for delivery throughout the area. Since the competitive battlefield in this business is speed of delivery, the parcels are divided among the trucks according to their geographical destinations to minimize the average time needed to make the deliveries.

On this particular morning, the dispatcher for the Blue River Valley Collection Center, Sharon Lofton, is hard at work. Her three drivers will be arriving in less than an hour to make the day’s deliveries. There are nine parcels to be delivered, all at locations many miles apart. As usual, Sharon has loaded these locations into her computer. She is using her company’s special software package, a decision support system called Dispatcher. The first thing Dispatcher does is use these locations to generate a considerable number of attractive possible routes for the individual delivery trucks. These routes are shown in the following table (where the numbers in each column indicate the order of the deliveries), along with the estimated time required to traverse the route.

Dispatcher is an interactive system that shows these routes to Sharon for her approval or modification. (For example, the computer may not know that flooding has made a particular route infeasible.) After Sharon approves these routes as attractive possibilities with reasonable time estimates, Dispatcher next formulates and solves a BIP model for selecting three routes that minimize their total time while including each delivery location on exactly one route. This morning, Sharon does approve all the routes.

The abstract formulation for this problem is below.

Let $y_j = 1$ if route $j$ is chosen, 0 otherwise

Let $x_{ij}$ be 1 if location $i$ is on route $j$ and 0 otherwise, for $i=A, \ldots , I$ and $j=1, \ldots, 10$ .

Let $c_j$ denote the time needed for the route $j$ , for $j=1, \ldots, 10$ .

Minimize $Z = \displaystyle \sum_{j=1}^{10} c_j y_j$

subject to:

$\displaystyle \sum_{j=1}^{10} x_{ij} y_j = 1, \text{ for } i=A, \dots, I$

$\displaystyle \sum_{j=1}^{10} y_j = 3$

$y_i \text{ binary, for } i=1, \ldots, 10$

Hints for 11-13

The order the locations are visited is not relevant, so you can make all the numbers in the table
into 1's and make the blanks into zeros. The structure of the code is similar to
t that in HW2.19-2.22.

Question 11 (Manually Graded) (10 points)

Use Pyomo solve this model. Use abstract code based on the formulation above.

In [0]:

Question 12 (2 points)

What is the minimum number of hours? (Round to 2 digits.)

Question 13 (2 points)

Which routes were chosen (select all that apply)?

Route 1
Route 2
Route 3
Route 4
Route 5
Route 6
Route 7
Route 8
Route 9
Route 10

Knapsack optimization

We'll revisit the Knapsack Optimization problem from previous lessons. This time, we'll solve it using integer programming.

Given a set of items, each with a weight and a value, use binary variables and Pyomo to determine which items to include in a collection such that the total weight is less than or equal to a given limit and the total value is as large as possible.

You will solve this problem twice, so you will write a function to modularize your code.

We will start with 20 items and you need to determine the collection of items that maximizes the value and keeps the total weight less than or equal to 50.

Use the problem data as described below:

Question 14 (Manually Graded) (4 points)

Write a function that accepts a numpy array of values, a numpy array of weights, and a maximum weight and returns the maximum value and the indexed variable of boolean choices (your "y" decision variable).

Your code should still work no matter how many items we are evaluating/optimizing. Use the starter code in the cell below.

Hints for integer programming for knapsack

Unlike our previous approaches to the knapsack problem. Here you're using 0's and 1's instead
of booleans. For example [1,0,1] means keep the first and third items in the knapsack.
The total value would be

1 * v_1 + 0 * v_2 + 1 * v_3

and the total weight would be
similar.

In [6]:

#solution
from pyomo.environ import *

def knapsack(values,weights,max_weight):
    '''
    Parameters:
    values: numpy array of values of each item
    weights: numpy array of weights of each item
    max_weight: maximum weight allowed in the knapsack

    Returns
    Final Value
    Final Weight
    The boolean variable (decision variable) values
    '''
    ### Add your code here

Hint (Not included in the quiz.)

If you call your function using the following values, you should get a total value of 25, total weight of 14, and the first two items should be included in your knapsack.

In [0]:

values_array = [10,15,20]
weights_array = [9,5,15]
max_weight_constant=14

finalVal, finalWeight, finalChoices = knapsack(values_array, weights_array, max_weight_constant)
# display
print(f'Total Value = {finalVal}')
print(f'Total Weight = {finalWeight}')

for i in range(len(values_array)):
    print(f'Include Item {i}? {["No","Yes"][int(finalChoices[i]())]}')

Question 15 (2 points)

The cell below generates the data for the problem with 20 items and a 50 lb weight limit. Run that cell, then call your function using the data generated.

What is the total value of the knapsack after optimization?

In [5]:

#Problem Data - random weights and values for knapsack problem 15 - do not change anything in this cell (Not included in Quiz/Solutions.)
import numpy as np
def gen_knapsack_data(num, val_range, weight_range):
    num_items = num
    np.random.seed(seed=8)
    values_array = np.random.randint(low=val_range[0], high=val_range[1], size=num_items)
    weights_array = np.random.randint(low=weight_range[0], high=weight_range[1], size=num_items)
    np.random.seed(
    )  # use system clock to reset the seed so future random numbers will appear random
    return values_array, weights_array

values_array, weights_array = gen_knapsack_data(20, [5,50], [1,10])
max_weight_constant = 50

Knapsack with more variables

Question 15 used just 20 variables. But we can increase the number of variables quite a lot with a straight binary problem like this before we run into issues with too much computational complexity. The sample data below generates 50000 possible items for the backpack. We'll also increase the weight limit to 500. This still runs for us in less than a minute on CoCalc.

Run your function to solve the problem with this data.

In [5]:

#Problem Data for Questions 16 & 17  - random weights and values for a knapsack problem - do not change anything in this cell. just run it (Not included in Quiz/Solutions.)
values_array, weights_array = gen_knapsack_data(50000, [5, 700], [1,1000])
max_weight_constant = 500

In [0]:

Question 16 (2 points)

What is the total value?

Question 17 (2 points)

How many items were chosen for the knapsack?