2020/21 EXAMINATIONS
MANAGEMENT SCIENCE
MSCI 534 Optimisation and Heuristics
Online examination
Target duration: 21⁄4 hours
We anticipate that this task should take students approximately 21⁄4 hours to complete. As the time taken to complete the task does not form part of the assessment criteria, and to take into consideration of students with additional needs, all students will be given 23hrs to complete the assessment task.
Available from 12noon on Monday 19th April 2021 and to be submitted by 11:00 on Tuesday 20th April 2021.
Submission requirements: Word is preferred but scanned versions are acceptable should you encounter any issues with Word.
You must answer THREE questions (out of FOUR).
You must work independently on this exam. You are not allowed to consult or have discussions with
other people. All work will be subject to plagiarism and malpractice checks.
You should also clearly state any assumptions that you have made in addition to those given in the questions.
You should also explain your reasoning carefully in each part of each question. Answers without adequate explanations will be awarded very few marks.
1
Question 1
a) Consider the following optimization problem
min 3𝑥2 +(𝑥 −1)4 +𝑒𝑥2−2 +(𝑥 −2𝑥 )2 11 21
s.t. 𝑥 ∈ R2
(i) Perform a single iteration of Newton’s method starting from initial point 𝑥0 = [1,2]𝑇.
(40 marks)
(ii) Determine whether your solution to (i) has converged if the stopping criterion of the algorithm is ‖∇𝑓(𝑥)‖ < 𝜀, with 𝜀 = 0.00001.
(10 marks)
b) The following quadratic programme represents a portfolio optimization problem with 𝑛 assets: 𝑛𝑛
min ∑∑𝜎 𝑥𝑥 𝑖𝑗 𝑖 𝑗
𝑖=1 𝑗=1
𝑛
s.t. ∑𝑟𝑥≥𝑅 𝑖𝑖
𝑖=1 𝑛
∑𝑥𝑖 =1 𝑖=1
𝑥𝑖 ≥ 0 for 𝑖 = 1, ... , 𝑛.
where 𝑥 is the proportion of funds invested in asset 𝑖, 𝑟 is the expected return of asset 𝑖, 𝜎 is the 𝑖 𝑖 𝑖𝑗
covariance of returns between assets 𝑖 and 𝑗 and 𝑅 is the desired minimum expected return of the portfolio.
(i) Name and briefly describe a technique that could be used to solve the quadratic program.
(20 marks)
(ii) Suppose that the problem has been solved in the previous time period and resulted in the portfolio 𝑥0 = [𝑥0, 𝑥0, ... , 𝑥0]𝑇 and in the current period we want to re-optimize our current
12𝑛
holdings 𝑥0. When re-optimizing the portfolio, there is a transaction cost 𝑡𝑖 proportional to the
amount of asset 𝑖 bought and a transaction cost 𝑡′ proportional to the amount of asset 𝑖 sold. Let 𝑖
𝑦𝑖 be the amount of asset 𝑖 bought and 𝑧𝑖 the amount of asset 𝑖 sold. State a new formulation for the problem which optimizes the portfolio 𝑥 by adapting the quadratic program above using the additional variables and new constraints appropriately (taking into account the transaction costs).
(30 marks)
2
Question 2
Masters Iron Foundry manufactures pig iron for use in the production of steel. They are a small operation and run a single blast furnace. This furnace heats the iron ore to a very high temperature at which the ore is smelted and liquid iron is produced. This liquid is then cooled to form pig iron. In an increasingly competitive market Masters want to reduce costs as far as possible. They have a large order for 1000 tons of pig iron from a new customer. They have extensive supplies of 3 types of ore: high grade, medium grade and cheap ore. Each has a different chemical composition, particularly iron and phosphorus content, as follows:
Ore grade
Premium
Medium
Cheap
Iron content (by weight)
50%
30%
10%
Phosphorus content (by weight)
2.5%
5%
15%
Cost per ton (£)
1000
700
100
The pig iron can be made by a combination of all three types; however, there are restrictions on the amount of phosphorus which can be safely handled by the furnace. No more than 5% of the material in the furnace (the combined ores) can consist of phosphorus.
a) Formulate this problem as a linear program.
(50 marks)
b) A bright employee has devised a way of reducing the phosphorus content of the cheap ore. It can be reduced from 15% to 10% at a cost of £400 per ton in a special reprocess that leaves the total weight of the cheap ore unchanged and the iron content at 10%. Unfortunately the process also requires a set up cost of £2000 if any cheap ore is reprocessed. Show how your formulation can be modified to include this new option.
(50 marks)
3
Question 3
Furness Feeds is a producer of animal feed. One of its products, Feed X, is made from four ingredients, which we denote here by A, B, C and D. The company wishes to find a minimum cost way of producing Feed X. One of its analysts has formulated this problem as the following linear program, in which the variables A, B, C and D represent the proportions of the four ingredients:
Minimise f = Subject to:
0.2 A + 0.35 B + 0.25 C + 0.8 D
0.2 A + 0.3 B + C + 0.8 D = 0.7
(Constraint 1) (Constraint 2) (Constraint 3) (Constraint 4) (Non-negativity)
OBJECTIVE FUNCTION VALUE 1) 0.5125000
VARIABLE A
B C D
ROW CON1) CON2) CON3) CON4)
V ARIABLE
A B C D
ROW
CON1 CON2 CON3 CON4
VALUE 0.250000 0.000000 0.250000 0.500000
SLACK/SURPLUS 0.000000
0.175000
0.000000
REDUCED COST 0.000000 0.143750 0.000000 0.000000
DUAL PRICES -0.062500
0.000000 -0.562500 -0.187500
A
+ 0.1 C
≥ 0.1 D ≥ 0.5
A + B + C + D = 1 and A, B, C, D ≥ 0.
The problem is solved using LINDO and the output is as follows:
0.000000
OBJ COEFFICIENT RANGES
CURRENT COEF 0.200000 0.350000 0.250000 0.800000
ALLOW ABLE INCREASE 0.164286 INFINITY 0.750000 INFINITY
ALLOW ABLE DECREASE INFINITY 0.143750 INFINITY 0.562500
ALLOW ABLE DECREASE 0.200000 INFINITY 0.500000 0.142857
RIGHTHAND SIDE RANGES
CURRENT RHS 0.700000 0.100000 0.500000 1.000000
ALLOW ABLE INCREASE 0.155556 0.175000 0.333333 1.000000
4
(a) Does this LP have alternative optima? Is it unbounded? Is it infeasible? Explain your answers.
(15 marks)
(b) Would the optimal solution change if the unit price of ingredient A increased from £0.20 to £0.30? What would happen to the optimal cost?
(25 marks)
(c) Would the optimal solution change if the minimum proportion of ingredient D (constraint 3) decreased from 0.5 to 0.3? What would happen to the optimal cost?
(25 marks)
(d) The company thinks that it could negotiate slightly lower prices for ingredient B. Do you think this would be worthwhile? Justify your answer.
(20 marks)
(e) What would be the effect on the optimal solution (and the optimal cost) if the costs of all four ingredients were to increase by 10%? Justify your answer.
(15 marks)
5
Question 4
A Charitable organisation periodically sends a van to a country in Eastern Europe. The van is filled with boxes; each box contains some gifts for children. The lorry can carry a total load of 160 kg, and it has a capacity of 125 cubic feet. There are two kinds of boxes they can take. A box of type A is worth £30, weighs 2 kg and occupies 2 cubic feet. A box of type B is worth £40, weighs 3kg and occupies one cubic foot. The charity wishes to maximise the total value of the boxes loaded on the van. This can be formulated as the following integer program:
max 30 A + 40 B
subject to:
2 A + 3 B ≤ 160 (weight limit) 2 A + B ≤ 125 (volume limit)
A, B 0 and integer.
The following tableau shows an optimal solution to the linear programming relaxation of this
problem, where s1 are s2 slack variables:
a) Generate Gomory cuts from the first and second rows of the tableau. Without doing any pivots, show that the two cuts are equivalent (i.e., they remove exactly the same part of the feasible region of the LP relaxation).
(30 marks) b) Add the Gomory cut corresponding to the second row to the tableau and reoptimise via a
dual pivot. Does this enable you to find the optimal integer solution?
(35 marks) c) Solve this problem by branch-and-bound instead. (Hint: You do not need to do any pivots.
Basis
ABs1 s2
RHS
A B
1 0 -1/4 3/4 0 1 1/2 -1/2
53 3⁄4 17 1⁄2
f
0 0 12 1⁄2 2 1⁄2
2312 1⁄2
Simple arithmetic is enough in this case.)
End of Paper
(35 marks)
6