Optimisation and Decision Making: Group Assignment 2020
Master in Business Analytics, Melbourne Business School
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 for- mulations (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 under- stand 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 so- lution 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}isafinitesetofnodesandE⊆V×V isasetofedges 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.
1
2
1
7
2
5
8
1
2
5
1
3
7
5
1
8
6
9
8
4
5
2
9
9
6
6
4
8
3
Table 1. A 3×3 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 9×9 table of numbers which must be filled according to the following rules:
• The table can be divided into 9 individual 3×3 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 9×9 grid, each number between 1 to 9 must be appear at least (and at most) once.
• Within any row of the 9×9 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
Figure 1. A 16×16 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 16×16 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}. Therulesareofthisgameareadirect extension of the rules for the standard Sudoku. Explain how would you change the ILP provided for the 3×3 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
3
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 exper- tises 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 fol- lows:
(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 indi- vidual 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 ∈ RN×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.
Goalie Goalie LR LR.
LL RR
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
−1 1 A= 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 yT = (y1, y2) (where the yT stands for the transpose vector of y).
• The vector selected by the goalie yT = (y1,y2) is communicated to the shooter.
• The shooter then chooses xT = (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.
-1
1
1
-1
1
-1
-1
1
Shooter
Shooter
6
Similarly, the expected payoff c of the goalie can be expressed in matrix form as c = yT (−A)x = xT (−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 xTAy, then the shooter wants to choose x to maximize xT Ay, giving him an outcome of
max xT Ay = max (−y1 + y2) (x1 − x2) . xx
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 xTAy can be written as
max xT Ay = max{(−y1 + y2) , (y1 − y2)}. x
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
The expected utility v of the shooter can be expressed in matrix form as v = xTAy
=x1 x2−1 1y1 1 −1 y2
= (−y1 +y2)(x1 −x2)
outcome will be
v = minmaxxTAy yx
= min (max{(−y1 + y2) , (y1 − y2)}) y
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,
c = minmaxxT(−A)y = maxminxTAy xy xy
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).
(6) Consider the same game but with the following payoff matrix
′ −2814 A= 30 −6
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.
Figure 2. Flow-shop diagram.
Task: an indivisible work-unit, each of them with a deterministic dura- tion. 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
Station 1
Station 2
...
Station n
7
Product to be processed Processed product
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) manufac- turing an amplifier. The product has 12 assembly tasks, each of them with a given duration (in minutes) and subjected to one or more precedence rela- tions, 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
2
3
4
5
6
7
8
9
10
11
12
Assembly box preparation
Printed circuit board (PCB) with power module assembly PCB with pre-amplifier assembly
Amplifier filter assembly
Push-pull circuit assembly
PCBs connections
Pre-amplifier circuit placement and welding
Connectors adjustments
Push-pull heat sink placement
Protection board placement
Electrostatic protection assembly
Finishing&Packing
3
6
7
6
4
8
9
11
2
13
4
3
- 1 1 2 2 2,3 3
6 4,5,8 8,11 7 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
Station 1 Station 2 Station 3 Station 4
In
Out
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 per- formed in any station as long as precedence relations are respected, we observe that such SH was valid when workforce was homogeneous and com- posed 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 geom- etry tasks. Furthermore, the RSW technique is also used for reinforcement welding and screw adding points, namely finishing and stud tasks, respec- tively. 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,
9
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.)
4
5
6
12
16 13 G
21
22
19 G
20 G
2 G
14 S
17 G
1
G 10
G 15
37 23
G
11 8G
9
18
Figure 5. Precedence diagram for a vehicle model. Geome- try (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)
1 2 3 4 5 6 7 8 9 10 11 12
1 1 1 1,2 1,2 1,2 1,2 1,2 1,2 1
1 1,2
57 38 50 42,63 27,41 55,83 43,65 43,65 64,96 63
39 38,57
13
14
15
16 17 18 19 20 21 22 23
1,2 3 1,2 1 1 1,2 1 1 1,2 1,2 1,2
37,56 77 21,32 71 45 37,56 32 52 33,50 51,77 52,78
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 perform- ing? (Hint: use variables to state which task is assigned to which station and performed by which robot. Notice that the actual pro- cessing 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 param- eters. 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
Consumer centre C
D
E
on the distance.
3 200 250 400
for product across
2 160 200 250 Table 4. Three month demand window
1 150 150 200
11
consumer centres.
12
Factory C D E
A $8 $6 $10
B $9$4$8
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 in- ventory.
(2) Modify the model from (1) to account for the fact that the trans- portation 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 and at most SMAX units of the lr lr
resource. A one-off cost, C S , is incurred when a farm with renewable resource lr
typer∈Rissetupatlocationl∈L;anditcostsCU foreachunitofthe lr
renewable resource type installed at the location.
Renewable resource locations and farm-size decisions are driven by de-
mand 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 elec- tricity” 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 pe- riod 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 CP 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 3
suppose G1 < A, G2 = A, and G3 > A. The total penalty for this example is given by CM(A−G1)+0+CP(G3 −A).
Formulate a mixed-integer linear program (MILP) that will locate the re- newable resources and determine their farm sizes such that the total farm establishment costs plus the total variability penalty is minimized, and de- mand for electricity is met.