代写MGMTMSA 408、代写Java，Python程序

日期：2023-04-17 08:39

MGMTMSA 408 – Operations Analytics

Homework 1 – LP Duality and Column Generation (Question Sheet)

Due April 19, 2023 (Section 2) / April 20, 2023 (Section 1) at 1:00pm PST

1 Semiconductor Manufacturing

A specialized semiconductor manufacturing plant produces three types of semiconductor chips.

Each chip requires a certain number of germanium (Ge) transistors and a certain number of silicon

(Si) transistors. In addition, each chip requires a certain amount of manufacturing time. Each chip

can be sold for a certain unit price. The requirements and prices of the chips are provided below:

Chip Type Num. Ge Transistors Num. Si Transistors Manufacturing Time Price

1 14 30 20 500

2 20 20 30 800

3 40 15 50 1000

In the above, the required number of transistors is presented in units of billions (e.g., the value of

14 for chip type 1 means that 14 billion germanium transistors are required). The manufacturing

time requirement is given in minutes, and the price is given in dollars.

The manufacturing plant has a total of 300 billion Ge transistors and 200 billion Si transistors

available. The plant also has 18 hours of manufacturing time available.

Part 1: LP Formulation

The plant is interested in deciding how much to produce of each type of chip, so as to maximize its

revenue.

a) Formulate the production problem as a linear program. What are the decision variables? What

is the objective function? What are the constraints?

b) Implement your linear program in Python using Gurobi.

What is the optimal objective value?

c) What are the optimal values of the decision variables?

Part 2: Dual Formulation

a) Write down the dual of the problem in Part 1. What are the decision variables? What is the

objective function? What are the constraints?

b) Implement your dual linear program in Python using Gurobi and solve it.

What is the optimal objective value?

1

c) What are the optimal values of the dual variables?

d) Verify that the optimal values you obtain here are the same as the shadow prices of the constraints

in the formulation you implemented in Part 1, which you can access by using the .pi attribute

of a Gurobi constraint reference.

Part 3: Shadow Prices / Marginal Analysis

a) To increase the plant’s revenue, a plant manager suggests increasing the amount of manufacturing

time by 10 hours. Will this change result in an improvement in revenue? Explain your answer.

b) A different plant manager proposes increasing the amount of available Ge transistors by 10

billion. Based on the shadow prices/optimal dual variables, what is your prediction of how

much the revenue will change from your answer in Part 1-b)?

c) Verify your answer to part b) by solving the primal LP from Part 1 with the right-hand side of

the Ge transistor constraint increased by 10.

(You can do this by reformulating the problem from scratch with a different right-hand side

value for the Ge transistor constraint. Another way is to use the following lines of code:

Ge constr.rhs = 310

m.update()

m.optimize()

where Ge constr is the reference to your Ge constraint, and m is the Gurobi model object. The

.rhs attribute of a constraint accesses the right-hand side / constant part of the constraint,

allowing you to modify your problem after you have built it.)

d) Suppose now that instead of increasing the amount of available Ge transistors by 10 billion, we

consider increasing it by 300 billion. Based on the shadow prices, what is your prediction of how

much the objective will change from your answer in Part 1-b)?

e) Check your answer in d) by solving the primal LP from Part 1 with the right-hand side of the

Ge constraint increased by 300. What is the change in revenue from your answer in Part 1-b)?

(You will find that it is not the same as the value in d).) What explains this discrepancy?

f) Lastly, suppose that instead of increasing only the amount of available Ge transistors, we consider

increasing the amount of available Ge transistors by 10 billion and the amount of Si transistors

by 20 billion. What is your prediction of the change in the objective from your answer in Part

2-b)?

g) Check your answer in f) by solving the primal LP from Part 1 with the right-hand side of the Ge

constraint increased by 10 and the right-hand side of the Si constraint increased by 20. What is

the change in revenue from your answer in Part 1-b)?

Page 2

2 Watch Company

A make-to-order watch company receives orders for different types of custom-made watches. The

company employs K = 20 different artisans, each of which can be used to complete each order. This

week, the company has received 100 orders. The company must decide how these orders should be

batched and assigned to each artisan. For convenience, let n = 100 and let us index each order by

a number from 1 to n = 100.

The key consideration in deciding how this batching should be done is that the production cost

of each artisan depends on the batch of orders assigned to them. While the production cost of a

batch is complicated, the company has determined that it can be reasonably approximated in the

following way. The production cost f(S), in dollars, of a batch S ? [n] when assigned to an artisan,

can be assumed to have the following functional form:

where ti is an estimate of the time in hours for an artisan to complete order i in isolation, and g is

the following piecewise-linear function:

Let us use [n] to denote the set {1, 2, . . . , n}. If the set of orders [n] is partitioned as [n] =

S1 ∪ S2 ∪ · · · ∪ SK , then the total production cost is f(S1) + f(S2) + · · ·+ f(SK). The goal of the

company is to solve the problem

minimize f(S1) + f(S2) + · · ·+ f(SK) (1a)

subject to S1 ∪ · · · ∪ SK = [n], (1b)

Sk ∩ Sk′ = k, k′ ∈ [K], k= k′. (1c)

In other words, determine how the orders should be divided among the K = 20 artisans, where

the artisans cover all of the n = 100 orders (this is constraint (1b)), and no two artisans overlap

in their assigned batches (or equivalently, no order is assigned to more than one artisan; this is

constraint (1c)), so as to minimize the total production cost (this is the objective function (1a)).

For simplicity, we will generate the estimated times t1, . . . , t100 randomly from a Uniform(0,3)

distribution. Use the code below to generate them:

import numpy as np

np.random.seed(50)

n = 100

t = np.random.uniform(0,3,n)

Part 1: Understanding the production cost function f

To begin, we will try to understand the mechanics of the costs. For the following parts, implement

a function calculateBatchCost which takes a list of indices in range(100), and outputs the value

of f(S).

Page 3

a) Suppose that orders 1, 3, 4, 8 are assigned to one artisan. What is the production cost arising

from this batching strategy (i.e., f({1, 3, 4, 8}))?

b) Suppose that no orders (i.e., S = ?) are assigned to one artisan. What is the production cost

arising from this batching strategy (i.e., f(?))?

c) Suppose that all of the orders are assigned to one artisan. What is the production cost arising

from this batching strategy (i.e., f({1, . . . , 100}))?

d) Suppose that the orders are equally divided, in order of their index, among five artisans. (In

other words, artisan 1 completes orders 1, . . . , 20, artisan 2 completes orders 21, . . . , 40, and

so on, up to artisan 5 who completes orders 81, . . . , 100.) What is the production cost arising

from this batching strategy?

Part 2: Heuristic approaches

Let us now test several heuristic approaches.

a) A random heuristic: Suppose that we randomly divide the orders among the 20 artisans. Suppose

that we repeat this 100 times, and calculate the total production cost. You might find the

following code snippet, which performs this random division once, useful:

import numpy as np

order_to_batch = np.random.choice(range(K), n)

batches = [ [i for i in range(n) if order_to_batch[i] == k] for k in range(K)]

cost_by_batch = list(map(calculateBatchCost, batches))

total_production_cost = sum(cost_by_batch)

Calculate the average cost of 100 repetitions of this procedure, with the random seed set to 200

beforehand. What is the average total production cost of this strategy?

b) A local search heuristic: Consider the following local search heuristic. We start with a random

assignment of orders to artisans, as in part a). For each order index i = 1, . . . , 100, we consider

calculating the new total production cost that would arise if we moved i from its current artisan,

say ki, to a new artisan k

′ ?= ki. We find the index of the new artisan, call it k?, that leads to the

lowest total production cost. If the new total production cost is lower than the current cost, then

we go ahead with the move; otherwise, we do not change the current batching strategy. We then

update the order index as i ← i + 1, and again attempt to move order i to a better artisan. If

we cycle through all n order indices without improvement, we conclude that the current solution

S1, . . . , SK is a locally optimal solution. We then repeat the overall procedure again at a new

random assignment.

To aid you, skeleton code for this procedure is provided in the file HW1 - Watch Company -

Skeleton Code.ipynb, with the parts that you need to fill in indicated in the comments.

What is the best (= lowest) total production cost attained by this procedure after 100 repetitions,

with the random seed set to 200 beforehand?

c) Can you claim that the solution obtained in part c) is the globally optimal solution of prob-

lem (1)? Why or why not?

Page 4

Part 3: A linear programming formulation

Let us now see how we can use linear programming to solve this problem. Define the decision

variable xS for each S ? [n], S ?= ?, which is 1 if there is an artisan assigned to the set of orders S,

and 0 otherwise. Let ai,S be 1 if order i is contained in the set of orders S, and 0 otherwise. Let

P([n]) denote the power set of [n], that is, the collection of all subsets of [n]. Then, the problem

can be formulated as the following integer program:

minimize

This problem is known as the set partitioning problem.

a) Suppose that n = 3. Write out the above formulation explicitly, without using sum (

∑

) notation,

replacing ai,S and f(S) with their numeric values. How many constraints are there? How many

decision variables are there? How many decision variables will there be when n = 100?

b) Based on your answer to a), explain how a solution of problem (2) can be used to obtain a

solution of problem (1), and vice versa.

c) Consider the following LP relaxation1 of the above problem:

minimize

Write down the dual of this problem. Hint 1 : You may find it useful to refer to the PDF note

on LP duality posted on BruinLearn. Hint 2 : Your formulation should have a decision variable

vector p = (p1, . . . , pn) and a scalar decision variable q.

d) We will now solve the dual using constraint generation. Explain why the separation problem is

max

where p = (p1, . . . , pn) is the vector of dual decision variables for the constraints (3b) and q is

the dual decision variable for constraint (3c). Hint : A constraint of the form aTx ≤ b in the

dual is equivalent to aTx? b ≤ 0.

1Note that we have relaxed the constraint xS ∈ {0, 1} to xS ≥ 0. Ordinarily, an LP relaxation of such a constraint

would additionally involve an upper bound of 1, i.e., we would write 0 ≤ xS ≤ 1. In this case, it turns out that xS

will automatically be upper bounded by 1; can you explain why?

Page 5

e) Explain how the separation problem (4) can be formulated as an integer program. Hint 1 :

Introduce a decision variable yi which is 1 if the set S includes order i, and 0 otherwise. Hint 2 :

For a convex piecewise-linear univariate function h defined as h(T ) = max{a1 + b1T, . . . , am +

bmT}, the problem

min

T

h(T )

can be reformulated as a linear program as follows: introduce a new auxiliary variable θ. Then

we can write

minimize.

Similarly, the problem maxT ?h(T ) can be written as

maximize≥ a1 + b1T,

...

θ ≥ am + bmT.

How can the function g be written as a maximum of three linear functions (viz. the same form as

h)? Hint 3 : Your formulation should include the binary decision variable vector y = (y1, . . . , yn)

and the continuous scalar decision variable θ (per the previous two hints).

f) Implement a constraint generation procedure to solve problem (3). Skeleton code is provided for

you in the file HW1 - Watch Company - Skeleton Code.ipynb. What is the optimal objective

value of the problem?

g) Let S denote the collection of batches that were generated in part f). Implement the primal

problem now, where P([n]) is replaced with S. What is the optimal objective value of this

problem? How many sets S ∈ S have a nonzero value of xS? Of those with a non-zero value,

how many have a value of xS strictly between 0 and 1?

h) Solve the primal problem again, but this time impose that the xS variables must be binary.

What objective value do you get? How does this compare to the optimal objective value in part

f) / part g)?

i) Recall that the original set partitioning problem (2) was an integer program. The problem that

we just solved via constraint/column generation is the LP relaxation of this problem. Based on

your answer to part g), can we now claim that the solution in Part 2d) is a globally optimal

solution of problem (1)? Why or why not?