Optimisation and Decision Making: Group
Assignment 2020
Master in Business Analytics, Melbourne Business School
Due date: April 15, 2pm
Instructions
The solution to the problems should take not more than 3 pages per
problem. All answers shall be self-contained with final conclusions, LP formulations
(where required) and brief explanations stated succinctly for each
problem. All code/spreadsheets are to be provided in an accompanying file
or appendix as supplementary material only. One should be able to understand
what you have done in the assignment without the need to open the
files/codes. The clarity of the explanations and the development of the solution
are as important as the solution itself. If you think the information
provided in a question is inadequate, please make reasonable assumptions
for answering it.
Problem 1: Graph Coloring (30 points)
Definition 1. A undirected graph G = (V, E) is an ordered pair in which
V = {1, . . . , n} is a finite set of nodes and E ⊆ V × V is a set of edges
where if (x, y) ∈ E, then node x is connected to node y. (This relationship
is reflexive: if x is connected to y then y is also connected to x).
Definition 2. A coloring of a graph G consist in assigning a number (or a
color) to each node, with the restriction that any two nodes that have an
edge in between cannot be assigned the same number (or color).
Definition 3. The chromatic number of a graph is k ∈ N if there exists
a coloring that uses k colors, but there is no coloring that uses less than k
colors. In other words, the chromatic number is the minimum number of
colors needed to have a coloring of a graph.
The chromatic number of a graph has many applications in Management
Science. Prominent examples are timetabling, scheduling, and assignment
problems.
Part 1:
(1) Explain in words a (very) trivial coloring algorithm for an undirected
graph with n nodes. Give an upper bound on the number of colors
needed for your coloring algorithm.
(2) Formulate the chromatic number problem of a graph G = (V, E),
V = {1, . . . , n} as an integer linear program. Use the upper bound
found above to set the maximum number of colors available.
Table 1. A 3x3 sudoku
(3) A graph is given in the file graph2020.dat. It contains 74 nodes
and 301 edges and one possible coloring uses only 14 colors. There
are, however, colorings of the graph that use less than 14 colors.
You must find the chromatic number of this graph. This is a hard
instance to solve, and it may take some time for the solver to come
with an answer, so be patient.
A Sudoku puzzle is a problem where there is an incomplete 9x9 table of
numbers which must be filled according to the following rules:
• The table can be divided into 9 individual 3x3 boxes. In each of
these boxes, every number (i. e., a color) between 1 to 9 must appear
at least (and at most) once.
• Within any column of the 9x9 grid, each number between 1 to 9 must
be appear at least (and at most) once.
• Within any row of the 9x9 grid, each numbers between 1 to 9 must
be appear at least (and at most) once.
Part 2:
(4) Suppose that you have available a costly and efficient software to find
the chromatic number of any given graph. In addition, this software
also allows you to force any vertex to have a specific colour. Explain
(in at most one page) how would you transform a Sudoku instance
into an instance of the coloring problem so that after your software
obtains a coloring on the constructed instance, you are able to easily
find a solution of the original Sudoku problem.
(5) Based on the integer linear programming formulation found in Part 1,
write down an ILP to solve the Sudoku given in Table 1. Provide
the solution as well as the complete formulation in paper (and also
provide the code).
(6) Suppose you are given a Sudoku S and a feasible solution s to it.
Based on the previous ILP (question item 5), write down an integer
linear programming formulation that returns 1 if the solution s to
3
Figure 1. A 16x16 sudoku
the Sudoku S is not unique and it is infeasible if the solution s is
unique for S.
(7) Using the previous ILP model (question item 6), determine whether
the Sudoku given in Table 1 has a unique solution.
(8) In a 16x16 Sudoku, there are 16 rows and 16 columns. Each cell
must contain one out of the following 16 symbols: {0, 1, 2, 3, 4, 5, 6,
7, 8, 9, A, B, C, D, E, F}. The rules are of this game are a direct
extension of the rules for the standard Sudoku. Explain how would
you change the ILP provided for the 3x3 Sudoku to solve this larger
game. Implement an ILP and solve the Sudoku in Figure 1. (You
don’t need to write all the ILP again in the assignment. You can just
explain how do you need to change it. Naturally, the source code of
your implementation must be provided).
Problem 2: A rostering problem (20 points)
A major metropolitan hospital is keen to improve the roster for its nursing
staff. They have three different shifts that is: early shift (ES) from 7:00 to
4
16:00, late shift (LS) from 13:00 to 23:00, and night shift (NS) shift from
22:00 to 8:00 on next day, and they employ nurses having four skill levels
which are proficient (4), competent (3), beginner (2), and naive (1). The
hospital requires that the minimum number of nurses with sufficient expertises
are available on each shift. The aggregate numbers of nurses required
on each shift type are R for ES or LS and RN for NS on working days, and
Rh for ES or LS and RNh for NS on other days (weekends and holidays).
Along with this, there are a number of other requirements which are as follows:
(1) Average skill level of the rostered nurses on each shift should be at
least competent. Here, average skill level is defined as the average of
skill levels of all the rostered nurses. For example, if only three nurses
each with the skill level proficient (4), competent (3), and beginner
(2) are scheduled for a shift, then the average skill level at that shift
is competent ((4 + 3 + 2)/3 = 3).
(2) There should be at least 50% proficient and no more than 20% naive
nurses on each shift.
(3) Nurses are rostered for no more than one shift per day.
(4) No nurse is rostered for two consecutive shifts. This means a nurse
cannot be scheduled for another shift immediately after he or she
finishes a shift.
(5) Nurses are rostered for at least four shifts each week, no more than
six shifts in a week, and no more than ten shifts in a fortnight.
(6) For each nurse, there must be at least four rostered days off in a
fortnight and at least two rostered days off each fortnight should be
together.
(7) The NS should be fairly assigned to all the nurses so that no individual
is scheduled for many night shifts.
Consider a set of all nurses Sn : {1, 2, 3, .., n} is given to you where the first
{1, .., n1} nurses belongs to naive (1) level, the next {n1 + 1, .., n1 + n2}
belongs to beginner (2) level, and so on. This means that there are n1
naive nurses, n2 beginner nurses, n3 competent nurses, and n4 expert nurses.
Furthermore, use a set of days Days : {1, 2, .., 14} where day 1 denotes the
first week’s Monday, 2 denotes the Tuesday and so on. Hospital pays $Cdw
for each ES or LS on working days, $Cnw for each NS on working days,
5
$Cdh for each ES or LS on other days, and $Cnh for each NS on other days.
Formulate a MIP model to develop a fortnight’s minimum cost roster.
Problem 3: Zero-Sum Game (20 points)
In game theory and economic theory, a zero-sum game with two players
is a mathematical representation of a situation in which each participant’s
gain (or loss) of utility is exactly the loss (or gain) of the utility of the other
participant.
Formally, each player can choose one action out of a set of N possible
actions. Let A ∈ R
N×N , be the payoff matrix. The payoff of player 1 is
defined as follows: Aij is the payoff of player 1, when player 1 chooses action
i and player 2 chooses action j. Given that we are in the case of a zero-sum
game, the payoff of player 2 is defined as follows: −Aij is the payoff of player
2, when player 1 chooses action i and player 2 chooses action j.
For example, consider a penalty shootout in a soccer game consisting of
a shooter (player 1) and a goalie (player 2). For simplification the ball can
only be shoot to the left or to the right. The payoffs of the shooter are
represented in the left table, and the payoffs of the goalie are represented in
the right table.
For instance, if the shooter shoots to the left and the goalie dives to the
right, shooter’s payoff is 1 and goalie’s payoff is -1. The payoff matrix of the
game is
A =−1 1 1 −1
Suppose the game is played sequentially as follows:
• The goalie chooses an strategy that consists in playing left or right
with certain probabilities. That is, the goalie with probability y1 ∈
[0, 1] will dive to the left and with probability y2 = 1 − y1 to the
right. We denote the goalie strategy as a vector y
T = (y1, y2) (where the yT
stands for the transpose vector of y).
• The vector selected by the goalie y
T = (y1, y2) is communicated to
the shooter.
• The shooter then chooses x
T = (x1, x2) knowing yT, where x1 ∈ [0, 1]
is the probability the shooter will shoot to the left and x2 = 1 − x1
is the probability he shoots to the right.
6
The expected utility v of the shooter can be expressed in matrix form as
v = x
T Ay=x1 x2−1 1
1 −1 y1 y2= (−y1 + y2) (x1 − x2)
Similarly, the expected payoff c of the goalie can be expressed in matrix form
as c = y
T(−A)x = x
T(−A)y = −v. Notice that the expected payoff of the
shooter is equal to minus the expected payoff of the goalie.
Since the shooter knows that the goalie has chosen y and knows that for
a given x, the outcome is x
T Ay, then the shooter wants to choose x to
maximize x
T Ay, giving him an outcome of
max
T Ay = max
x(−y1 + y2) (x1 − x2).
Notice that if (−y1 + y2) ≥ 0, then the optimal strategy of the shooter is
x1 = 1, x2 = 0. If (−y1 + y2) < 0, then the optimal strategy of the shooter
is x1 = 0, x2 = 1. Therefore, v = maxx x
T Ay can be written as
max
T Ay = max{(−y1 + y2),(y1 − y2)}.
Where max{x, y} is a function that returns x if x ≥ y and y otherwise.
Since the goalie knows what the shooter will do and will know the given
outcome, he chooses to minimize the payoff of the shooter. Thus, the final
outcome will be
The minimizing y above is called the min max strategy.
(1) Formulate a linear programming (LP) model to find the optimal
min max strategy y. Hint: Notice that the objective function is
not linear, so consider using an auxiliary variable v to represent
max ((−y1 + y2),(y1 − y2)) using two constraints.
(2) Solve the above linear programming model.
(3) Now consider that the shooter chooses his strategy x first and then
the goalie selects his action y, knowing x. In this case, the shooter
will choose a strategy x, such that,
That is, the shooter will choose a max min strategy. Formulate the
linear programming model to find the max min strategy x.
(4) Notice that the LP in part (1) is the dual of the LP in part (3). Using
this fact, what can you say about the optimal objective value of the
second LP based on the solution obtained in part (2)?
(5) Solve the LP model of part (3).
7
(6) Consider the same game but with the following payoff matrix
Find the min max strategy y and the max min strategy x with this
new payoff matrix.
Problem 4: Robotic Assembly Line Balancing (30 points)
An assembly line is a product-oriented layout with workstations placed in
a sequential and linear order, also known as flow-shop. They are commonly
employed in high-volume industries to produce standardised products. A
flow-shop diagram is shown in Figure 2. The pace in such lines is dictated
by the most loaded station, namely the bottleneck. The terminology applied
to understand the assembly line balancing problem is hereafter presented.
Station 1 Station 2 ... Station n
Product to be processed
Processed product
Figure 2. Flow-shop diagram.
Task: an indivisible work-unit, each of them with a deterministic duration.
Each task must be assigned to only one station.
Duration of tasks: the time necessary to perform a given task. The
processing time in a station is the sum of the task durations assigned to it.
Precedence relations between tasks: sequence or order in which tasks
must be performed given by a partial ordering graph.
Precedence graph: a graph constructed from the precedence relations
to better visualise their order. Tasks are represented by circles, its index
by the number inside the circle, and arrows represent precedence relations.
Figure 3 illustrates a precedence graph. For example, in order to perform
task 6, both tasks 2 and 3 must have been performed. To perform task 8,
task 6 has to be performed and, consequently, tasks 1, 2, and 3 as well.
Station: a physical location where a particular set of tasks is performed.
Stations in an assembly line are displayed as a flow-shop and are generally
linked by conveyor belts. Each station processes only one task at a time.
Cycle time: line’s output rate. For instance, if an assembly line produces
120 units of a given product in one hour, its throughput rate is 2 units/minute
and, consequently, its cycle time is 0.5 minute/product. As stations layout
is sequential, the cycle time is determined by the most loaded station, i.e.
by the station that has the greatest sum of task processing times
A common simplification found in the Simple Assembly Line Balancing
Problem (SALBP) is that all stations are capable to perform any task. With
8
this idea in mind, the concept of a SALBP is to assign all tasks to stations in
an assembly line while respecting precedence relations. As for the objectives,
the type-1 version (SALBP-1) aims at the minimisation of stations when
production rate requirements are fixed, for example, when the demand is
known and must be met. On the other hand, the type-2 (SALBP-2) aims at
the minimisation of the cycle time (and therefore maximisation of production
rate) given a certain number of available stations.
The following example shows an electronic industry (Amp-Opt) manufacturing
an amplifier. The product has 12 assembly tasks, each of them with
a given duration (in minutes) and subjected to one or more precedence relations,
which are specified in Table 2. The precedence graph is presented in
Figure 3.
Table 2. Task and predecessor list for an amplifier.
Task Description Duration Predecessor(s)
1 Assembly box preparation 3 -
2 Printed circuit board (PCB) with power module assembly 6 1
3 PCB with pre-amplifier assembly 7 1
4 Amplifier filter assembly 6 2
5 Push-pull circuit assembly 4 2
6 PCBs connections 8 2,3
7 Pre-amplifier circuit placement and welding 9 3
8 Connectors adjustments 11 6
9 Push-pull heat sink placement 2 4,5,8
10 Protection board placement 13 8,11
11 Electrostatic protection assembly 4 7
12 Finishing&Packing 3 9,10
Figure 3. Precedence graph for an amplifier.
The manager of this assembly line wished to distribute (assign) these
tasks to 4 stations and minimise the cycle time (workload in the bottleneck
station), resulting in a SALBP-2 instance. Figure 4 illustrates the scenario
under study:
The optimal solution in this case would be a cycle time of 20 minutes,
with tasks 1, 2, 3 and 5 assigned to station 1; 6 and 8 to station 2; 4, 7 and
9 to station 3; and 10, 11 and 12 to station 4. However, as this assembly
9
In Out
Station 1 Station 2 Station 3 Station 4
Figure 4. Assembly line balancing problem under study.
line only works 8 hours per day on business days, such production rate is
not enough to meet the monthly demand of 600 units for their amplifiers.
Considering 20 business days per month:
Part 1:
(1) How many amplifiers per month can Amp-Opt manufacture with the
current configuration (4 stations)? What is the minimum cycle time
Amp-Opt has to achieve to meet its demand?
(2) Formulate an integer linear programming (ILP) model for the SALBP-
1 and solve it with the required cycle time to meet the demand.
Present your model by explaining all your variables, constraints and
parameters. (Hint: use variables to state which task is assigned to
which station and precedence constraints for each pair of tasks)
(3) The solution should describe how many stations is required to achieve
the minimum cycle time, as well as where each task has been assigned
to.
Multiple Types of Robots
By revisiting the simplification hypothesis (SH) that tasks can be performed
in any station as long as precedence relations are respected, we
observe that such SH was valid when workforce was homogeneous and composed
of humans. Nonetheless, modern assembly lines heavily rely on robotic
labour to execute tasks. In particular, the automotive industry employs
robots for precision, quality, and security reasons. This new feature gives
rise to the Robotic Assembly Line Balancing (RALB) problem.
For instance, the Resistance Spot Welding (RSW) technique is widely used
in order to perform welding tasks in the body-in-white stage, in which the
car’s “body” is built. This process unites metal sheets by using welding guns.
Metal sheet joining tasks must respect geometric tolerances, demanding high
quality robots and tools for precision purposes. Such tasks are called geometry
tasks. Furthermore, the RSW technique is also used for reinforcement
welding and screw adding points, namely finishing and stud tasks, respectively.
Differently from geometry tasks, these ones do not require strict
assurance for geometric tolerances and can be performed by simpler robots.
Finishing tasks can be performed by either this simpler (and cheaper) robot,
or by the most precise (and more expensive) one in less time. Stud tasks,
10
however, require a specific tool, and therefore these tasks must be exclusively
performed by robots equipped with the stud gun.
Figure 5 is the precedence graph of a given car model produced in the
company under study, geometry and stud tasks are indicated in the graph.
Table 3 presents the task durations of that model, where geometry tasks are
bold-faced, stud tasks are italicised, and the remaining ones are finishing
tasks – higher processing times are for the cheaper robot. The prices of the
most precise robot (Robot 1) and its cheaper version (Robot 2) to perform
welding tasks are $20 and $10 monetary units, respectively, while the price
for the stud robots (Robot 3) is $18 monetary units. The cycle time for this
line is 250 time units. (Note: these data has been normalised from the actual
values to preserve industrial confidentiality.)
Figure 5. Precedence diagram for a vehicle model. Geometry
(G) and Stud (S) tasks are indicated in the graph, while
the remaining ones are finishing tasks.
Table 3. Task durations (time units) for a vehicle model.
Task Robot(s) Duration(s) Task Robot(s) Duration(s)
Part 2:
(1) In this context, the objective for a type-1 RALB problem is no longer
the minimisation of stations. When the desired production rate is
given, the objective is to minimise the total cost to implement such
assembly line. Formulate an integer linear programming (ILP) model
for this problem and solve it with the required cycle time to meet
the demand. Present your model by explaining all your variables,
constraints and parameters. Which assortment of robots did you
choose? Where are they assigned to? Which tasks are they performing?
(Hint: use variables to state which task is assigned to which
station and performed by which robot. Notice that the actual processing
time depends on the robot you are using.)
(2) Now supposed that you have a limited budget of $90 monetary units
to built your robotic assembly line. Modify your previous model to
tackle this problem and solve it with the budget limitation. Present
your model by explaining all your variables, constraints and parameters.
Which assortment of robots did you choose? Where are they
assigned to? Which tasks are they performing?
(3) Assume this assembly line has a 2-year lifespan and works 20 business
days per month and 8 hours per day. After this time, the model has
to be updated to a new version and the robots replaced. You have
been given a flexible budget to spend between $80 and $100 monetary
units in building the line. Each unit of the manufactured product
gives you a profit of $0.12. What budget should you ask for in this
range ($80 to $100)? Explain your decision in detail. Consider each
time unit to be equivalent to one minute and unlimited demand.
Problem 5: Distribution problem (20 points)
A company produces the same product at two different factories (Factories
A and B), and then the product has to be shipped to three consumer centers
(C, D and E). The monthly production capacities of the factories A and B
are 400 and 300 units, respectively. The unitary production cost at factories
A and B are $8 and $10, respectively. A maximum of 100 units of inventory
can be held in each factory, at a cost of $1.50 per unit of the product per
month. Each consumer centre has a known demand for the product, and
there are different costs associated with transporting products from each
factory to each consumer center, depending on the distance.
Consumer centre 1 2 3
Table 4. Three month demand window for product across
consumer centres.
Table 5. Transportation costs (per unit) from factories to
consumer centers.
Questions.
(1) Write a linear program to model and find the optimal distribution
plan to ensure that demand at the consumer centers is met while
minimising the combined cost of production, transportation and inventory.
(2) Modify the model from (1) to account for the fact that the transportation
cost between a factory and a center in a period is given by
a fixed amount of $200 per month1 plus the cost of transportation
per unit.
(3) Modify the model from (2) to account for the fact that you can ship
products from one factory to the other with a cost of $2 per unit
transported.
Problem 6: Energy provision (20 points)
The state of Victoria primarily relies on brown coal sources for electricity
generation. Here, we wish to consider a simple variant of the problem of
introducing, locating and sizing renewable energy resources, namely wind
and solar farms, hydro power, and biomass plants, in the state of Victoria.
Let L = {1, 2, . . . , n} be the set of candidate locations in Victoria and
R = {W ind, Solar, Hydro, Biomass} be the set of renewable resource types.
At most two renewable resource types are to be installed at any candidate
location l ∈ L. If some renewable resource type r ∈ R is installed at location
l ∈ L, we need to allocate at least SMIN
lr and at most SMAX
lr units of the
resource. A one-off cost,
lr, is incurred when a farm with renewable resource
type r ∈ R is setup at location l ∈ L; and it costs C
lr for each unit of the
renewable resource type installed at the location.
Renewable resource locations and farm-size decisions are driven by demand
for electricity and the prospect/potential of a location for renewable
energy generation. For this simple problem variant, the renewable resources
are not to be used to replace existing brown coal generation sources, but are
instead used to cope with demand fluctuations beyond the base electricity
supply generated by brown coal sources. Therefore, the “demand for electricity”
is defined here as the amount of electricity to be supplied solely by
the renewable resources.
Let the set of discrete, equally-sized, time periods be T. Each time period
may, for example, represent a 30-minute interval and the length of the
1That must be paid if there is transportation between the factory and the center.
13
planning horizon could be 5 days – in this case T = {1, 2, 3, . . . , 239, 240}.
Let Dt be the demand for electricity at time t ∈ T. Each location l ∈ L can
produce Plrt amount of electricity during time t ∈ T per unit of renewable
resource type r ∈ R installed.
The total renewable energy generation must be at least Dt for all t ∈ T.
There is a further requirement that the variability of the total renewable
energy generation be “reasonable”. To achieve a “reasonable” variability, any
deviation from the total average generation for any given day is penalized
as follows: one unit of positive deviation is penalized at C
P and one unit of
negative deviation is penalized at CM. For instance, consider a three-period
example with total renewable generations G1 , G2 and G3 on time periods
1, 2, and 3, respectively. The average total generation is A =G1+G2+G3
and
suppose G1 < A, G2 = A, and G3 > A. The total penalty for this example
is given by CM(A − G1) + 0 + C
P (G3 − A).
Formulate a mixed-integer linear program (MILP) that will locate the renewable
resources and determine their farm sizes such that the total farm
establishment costs plus the total variability penalty is minimized, and demand
for electricity is met.
版权所有：编程辅导网 2021 All Rights Reserved 联系方式：QQ:99515681 微信：codinghelp 电子信箱：99515681@qq.com
免责声明：本站部分内容从网络整理而来，只供参考！如有版权问题可联系本站删除。
