共计 11707 个字符，预计需要花费 30 分钟才能阅读完成。
QBUS2310 Management Science
Assignment 2
Semester 1, 2022
Out: 2nd May 2022
Due: 23rd May 2022 at 11:59pm
Instructions
This assignment consists of five problems, some involving multiple parts. Some parts require a written
response and others involve coding. The parts that require a written response are described in this
document, while the coding questions are described in the associated Jupyter notebook (.ipynb file).
When a problem asks you to formulate a model, you need to provide your mathematical formulation
with clear justification of variables, constraints and objective. If you decide to label any of the data with
algebraic symbols, you must clearly define these (e.g., let aij be the amount of material i required by
product j).
The written parts have to be typed up. This means no handwriting and no screen shots. If you are using
MS Word, use the equation editor to make your mathematics look pretty. We recommend using LATEX or
a similar system for typesetting your answer.
You should submit a PDF to GradeScope for the written parts and match the page number with the
questions that you answered. You can find the detailed instructions on how to scan and submit your
assignments through GradeScope on Canvas. If you fail to match the page to the corresponding question,
the marker will not be able to view your response and thus you will be awarded 0 marks for the question.
You should answer the coding questions by modifying the Jupyter notebook appropriately, and submit it
through Canvas.
All the problems can be done using only the material from this class, and we will deduct points from
solutions that refer to outside material.
Question: 1 2 3 4 5 Total
Points: 15 15 25 20 25 100
i
QBUS2310 Assignment 2 Due 23rd May 2022
- Tournament elimination via integer programming. Suppose we have n teams competing in a tournament.
The teams will play every other team some number of times, and each outcome will be win-lose (no draws).
The winner is the team that has the highest number of overall wins; for simplicity we will allow for more
than one winner in the event of ties, and each game must end in win or loss (no draws). At certain points in
the tournament, we wish to determine which teams are eliminated, meaning they have no chance of being
the winner. The data available at a given point is the following:
wi, the number of wins so far for each team i.
rij , the number of games remaining to be played between teams i and j. Note that these are fixed
numbers, not decision variables.
We say that team k is eliminated if we can guarantee that there is at least one other team that will finish
with a better record than them, given that they win all of their remaining games. In other words, even if
team k finished with the best possible wk +
∑
j rkj wins given the remaining schedule, there will always be
at least one other team that has strictly more wins than k, regardless of how other results play out.
An easy condition to check for elimination is that there exists wi > wk +
∑
j rkj . However, this is not the
only condition. For instance, if k has 22 wins and no games left to play, but there are two teams i and j
with 21 wins who must play each other three times, then at least one of i and j will finish with 23 or more
wins (regardless of the results, since one team must win at least 2 games), eliminating k.
The subtlety is that eliminating k depends on more than just the head-to-head record between k and other
teams. It also depends on how other teams perform against each other. There are numerous combinations
for how other results will play out, and checking each one manually is a daunting task. However, by
organising this in an integer programming model, and then a network flow model, we can solve this using
existing machinery.
In this question, we will formulate an integer programming model for determining whether a given team k
is eliminated or not.
Let zi be the number of wins for team i from remaining games, assuming that team k has won all of the
remaining games. Team k is eliminated if, for all possible outcomes, We
wish to describe all feasible outcomes zi for i ?= k using linear constraints. If we can do this, then we can
check whether k is eliminated simply by minimizing the maximum over all feasible outcomes.
We will define xij,i to be the number of times that i wins over j in their remaining games. We will use the
notational convention that xij,i = xji,i and xij,j = xji,j .
(a) (3 points) Note that xij,i should be an integer variable. What are bounds on xij,i?
(b) (3 points) Relate xij,i and xij,j with a linear constraint (involving rij).
(c) (3 points) Relate zi and xij,i with a linear constraint.
(d) (6 points) Formulate an optimization model that can be used to determine whether k is eliminated or
not, and explain how we would use it. - Tournament elimination via network flows. Consider the same tournament elimination problem as question
1, where we built a linear program to check whether a given team k is eliminated or not. Solving an integer
program for this is doable, but is unnecessary for this problem. We will use the important property of
network flow models minx
{
c?x : Ax = b, 0 ≤ x ≤ u} that when using integer data b, u, the optimal flow
solutions will be integer as well, where A is the node-arc incidence matrix of some network.
(a) (2 points) Consider a bipartite network where nodes on the left side represent pairs of teams with
games remaining, and the right side represents teams. Explain how variables xij,i can represent arcs
in this network.
(b) (2 points) How can variables zi be incorporated into the network?
(c) (2 points) We need to represent the constraint relating xij,i and xij,j in our network. How can we do
this? (Think about exploiting flow balance constraints.)
(d) (2 points) Similarly, explain how to represent the constraint relating zi and xij,i.
(e) (3 points) Modelling maxi ?=k{zi + wi} is not possible with a network model. But to check that k is
not eliminated, we don’t need to model the maximum fully, we just need to check that it’s less than
wk +
∑
j rkj , which is the same as zi + wi ≤ wk +
∑
j rkj for each i ?= k. Explain how this can be
incorporated into the network model.
(f) (4 points) Define missing components of the network model (if any) and explain how solving it deter-
mines whether k is eliminated or not.
Page 1 of 4.
QBUS2310 Assignment 2 Due 23rd May 2022 - (25 points) Please see the Jupyter notebook for further details. Implement the tournament elimi-
nation model in Gurobi by completing the given functions in the Jupyter notebook. - Team formation. In this problem, we will consider a team formation problem where we need to assign agents
to different teams in order to maximize utility.
Suppose that you are a unit coordinator running a unit with a group work assessment. In this class, you
have n students and need to form T different teams of size t and for simplicity, assume that n = Tt. We can
express the friendship status between the students through an undirected graph G = (V, E) with V = [n]
and {(i, j), (j, i)} ∈ E if student i is friends with student j. Additionally, define U to be a symmetric n× n
matrix of utilities, where Uij denotes the utility when student i is in a group with student j (which may be
negative as there may be conflict between students) and assume that U has 0s on the diagonal for simplicity.
Note. In the rest of the problem, please ensure that your final answer can be added to an IP to solve the
problem, i.e., all functions are linearly representable.
(a) (4 points) Define xik to be whether student i is in group k. What constraints do we have on this
variable?
(b) (4 points) Let yijk = xikxjk be a binary variable which is on if both students i and j are in team k.
Clearly, we also have yijk = yjik. What linear constraints can we add to model this?
To promote diversity, you plan to form teams such that each team has at most m different friendship
pairs. How can you model this as a IP?
(c) (4 points) Now, to further promote diversity, you plan to form teams such that each student knows at
most p students in their group beforehand. Using yijk, what linear constraint allows us to model this?
(d) (4 points) The utility for each group is defined to be the sum of all the pairwise utilities between all
the students in each team, which has an upper bound of Umax for each team. (You can think of this
being the maximum mark attainable.)
Suppose you want to maximize the lowest utility over all teams. How can you model this as a IP?
(e) (4 points) Now suppose that each team is required to perform a different task. For example, a pro-
duction where one team is responsible for lighting, one for sound, etc. Now you have T different utility
matrices, denoted U (k), k ∈ [T], where U (k)ij is the pairwise utility of having students i and j perform
task k. Assume that the total utility of a group is calculated in the same way as described in part (d)
where the total utility for each task is capped at Umax.
Suppose you now want to maximize the total utility across all tasks. How would you model this? - Chance constraints and the big-M technique. We consider a stochastic variant of the production planning
problem.
Recall that we have n products indexed by j ∈ [n] and m materials indexed by i ∈ [m]. We decide amounts
xj for each product j to produce. Each unit of product j requires aij units of material i. We define
ai = (ai1, . . . , ain) ∈ Rn for each i ∈ [m], and x = (x1, . . . , xn) ∈ Rn. We obviously require x ≥ 0. We
will consider the simple case without holding costs, and assume that any amount xj of product j that
we produce can be sold for cjxj profit. Thus letting c = (c1, . . . , cn), the total profit of our plan is cx.
Ordinarily, we know the amount bi of material i we have available, and choose x so that a
i x ≤ bi for each
i ∈ [m]. Thus we would ordinarily solve
max
x
cx
s.t. x ≥ 0
a?i x ≤ bi, i ∈ [m].
In the stochastic variant, however, the vector b = (b1, . . . , bm) ∈ Rm is not known exactly. Instead, we
are given N possible scenarios for the b vector, which we label b1, . . . , bN . Note that bki is the amount of
material i ∈ [m] available in scenario k ∈ [N]. We assume that each scenario has equal probability 1/N of
occurring.
In chance-constrained programming, we use this data in the following way. Let b? ∈ Rm be the random
vector that equals bk with probability 1/N , for each k ∈ [N]. Fix some p ∈ [N]. We will require that our
production plan x satisfy the chance constraint
P
[
a?i x ≤ b?i, ?i ∈ [m]
]
≥ p
N
,
Page 2 of 4.
QBUS2310 Assignment 2 Due 23rd May 2022
i.e., we wish to choose the production plan x so that the production constraints Ax ≤ bk are satisfied for
at least p out of N scenarios bk. Thus we solve the following model:
max
x
c?x
s.t. x ≥ 0
P
[
a?i x ≤ b?i, ?i ∈ [m]
]
≥ p
N
.
Note: this model does not specify which of the scenarios should be satisfied; instead, we let the optimization
model make this choice for us, in a way that maximizes the profit c?x.
In parts (a) and (b), we will derive a linear formulation for the chance constraint P
[
a?i x ≤ b?i, ?i ∈ [m]
]
≥
p/N . Then in part (c) and (d), we will implement it in Gurobi.
(a) (4 points) For each scenario k, introduce a binary variable zk ∈ {0, 1}. We can use the big-M technique
to write a set of constraints that are equivalent to the following implication:
zk = 0 =? Ax ≤ bk.
In other words, you want to ensure that when zk is set to 0, we will enforce each of the constraints
a?i x ≤ bki for each i ∈ [m]. This can be done by adding the linear constraints
a?i x ≤ bki +Mki zk ?i ∈ [m],
for some large enough constants Mki .
Assuming that aij > 0 and b
k
i ≥ 0 for all i ∈ [m], j ∈ [n], explain why
Mki = max
j∈[N]
bki /aij
are valid big-M values.
(b) (2 points) Together with the constraints from part (a), give a constraint on the z vector that is required
to ensure the chance constraint P
[
a?i x ≤ b?i, ?i ∈ [m]
]
≥ p/N holds.
(c) (6 points) Please see the Jupyter notebook for further details. Implement the chance con-
strained production planning model in Gurobi by completing the given functions in the Jupyter note-
book.
(d) (2 points) On the given data in the Jupyter notebook, run the model you implemented in part (c) and
report the runtime. You might want to run the code a couple of times and average the times. You do
not need to submit the code for this, just report the runtime.
If we can find smaller but still valid big-M constants, then the runtime of the model will improve. Parts
(e) to (g) will investigate a method to do this, and compare the runtime with part (d).
To this end, for each i ∈ [m], define the set
Qi =
?????????(x, z) ∈ R
n × RN :
zk ∈ {0, 1}, k ∈ [N]
a?i x ≤ bki +Mki zk, k ∈ [N]∑
k∈[N]
zk ≤ N p.
In other words, (x, z) ∈ Q whenever each entry of z is binary, the sum of the entries of z is at most N p,
and whenever zk = 0, x satisfies a
i x ≤ bki .
The Qi are related to our model in the following way: x satisfies P[Ax ≤ b] ≥ p if and only if
there exists a binary vector z ∈ {0, 1}N such that (x, z) ∈
i∈[m]
Qi.
You should convince yourself that this is true (but you don’t need to submit anything for it).
(e) (4 points) Fix some i ∈ [m]. Define bˉ(p)i to be the pth largest value amongst b1i , . . . , bNi . Show that if
(x, z) ∈ Qi, then it satisfies the constraint
a?i x ≤ bki +
(
bˉ
(p)
i ? bki
)
zk, ?k ∈ [N].
Page 3 of 4.
QBUS2310 Assignment 2 Due 23rd May 2022
Hint: to do this, fix a point (x, z) ∈ Qi and k ∈ [K]. Show that when zk = 0, then a?i x ≤ bki is
satisfied. Then show that when zk = 1, a
?
i x ≤ bˉ(p)i is satisfied.
This shows that we can replace the old big-M values Mki from part (a) with new big-M values Mˉ
k
i =
bˉ
(p)
i ? bki .
(f) (3 points) Please see the Jupyter notebook for further details. Implement the chance con-
strained production planning model in Gurobi by completing the functions in the Jupyter notebook.
You should implement your model with the new big-M values Mˉki = bˉ
(p)
i ? bki .
(g) (4 points) On the given data in the Jupyter notebook, run the model you implemented in part (f) and
report the runtime. You might want to run the code a couple of times and average the times. You do
not need to submit the code for this, just report the runtime. Comment on the differences between the
runtimes compared to the differences between the big-M values. What is the“extra bit of information”
that we used to derive the new values Mˉki in part (e) compared to the original values M
正文完
