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?