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.

1.  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 +Pj 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 +Pj 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, maxik{zi + wi} > wk +Pj rkj. 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.

2.  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 maxik{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 +Pj rkj, which is the same as zi + wi  ≤ wk +Pj 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.

3.  (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.

4.  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)  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?

5.  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 c⊤x. Ordinarily, we know the amount bi  of material i we have available, and choose x so that ax ≤ bi  for each i ∈ [m]. Thus we would ordinarily solve

max

c⊤x

x ≥ 0

ax ≤ 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 bi(k)  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  ∈ 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 hax ≤ i , ∀i ∈ [m]i ≥  ,

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

c⊤x

x ≥ 0

P hax ≤ i ,

∀i ∈ [m]i ≥  .

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 hax ≤ i , ∀i ∈ [m]i ≥

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 ax ≤ bi(k)  for each i ∈ [m]. This can be done by adding the linear constraints

ax ≤ bi(k) + Mikzk     ∀i ∈ [m],

for some large enough constants Mik .

Assuming that aij  > 0 and bi(k)  ≥ 0 for all i ∈ [m], j ∈ [n], explain why

Mik  = max bi(k)/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 hax ≤ i , ∀i ∈ [m]i ≥ 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

zk  ∈ {0, 1}, k ∈ [N]           

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 ax ≤ bi(k) .

The Qi  are related to our model in the following way: x satisfies P[Ax ≤ ] ≥ p if and only if

there exists a binary vector z ∈ {0, 1}N  such that (x,z) ∈  \  Qi .

(e)  (4 points) Fix some i ∈ [m]. Define p)  to be the pth largest value amongst b,...,bi(N).  Show that if

(x,z) ∈ Qi, then it satisfies the constraint

ax ≤ bi(k) + p) − bi(k)  zk ,    ∀k ∈ [N].