COMP3910: Coursework 2
Submission: Gradescope
Deadline: 17:00 GMT, Friday 25 March 2022
Award: This piece of summative coursework is worth 10% of your grade
Problem 1 (modelling) [12 marks]
A company needs to purchase components X and Y to produce toys. Components X and Y can
be purchased from three suppliers, A, B and C. The purchase costs of the components are detailed
in the middle part of the table below. The required quantities of the components are shown in the
last column.
Cost Supplier Total
per unit A B C requirement
Component X £ 54 £ 56 £ 61 400
Component Y £ 120 £ 110 £ 106 500
Delivery per order £ 75 £ 80 £ 70
The following requirements should be satisÖed.
(i) Each supplier has a Öxed delivery charge for the whole order, independent on the size of the
order and the product types. Delivery charges are shown in the last row of the table.
(ii) Supplier C has a minimum order size of at least 100 units of components Y (if a non-zero
amount of components Y are ordered from C).
(iii) Supplier A will only accept an order which is worth at least £ 25,000, without taking into
account delivery charges and independently on the component type (components X, components
Y, or both).
The objective is to arrange the supply of the required components minimising the total cost.
Formulate an ILP. No need to present an explanation.
Use variables xA, xB and xC for the number of components X purchased from A, B and C,
respectively.
Similarly, use variables yA, yB and yC for the number of components Y purchased from A, B and
C, respectively.
You may need additional variables in your model.
1
Problem 2 (B&B for the knapsack problem) [28 marks]
An energy company has n = 4 electricity generators, each of which can be regulated independently
of one another. Each generator can be either switched o§ or it can operate in one of the two
modes: at a normal rate, as indicated in the table below, or at a double rate, producing double
power output at a double cost.
The following table shows the cost to operate each generator at a normal rate and the power
output.
Generators Demand
i = 1 i = 2 i = 3 i = 4 b
Operating cost ci 14 13 10 12
(in thousands of pounds)
Power output ai 10 7 4 3 12
(in Gigawatt)
The company wishes to select generators and their operation modes in order to meet the expected
12 Gigawatt demand at the smallest possible operating cost. The corresponding problem can be
modelled as the knapsack problem with the cost minimisation objective:
min f =
Pn
i=1
cixi
s.t. Pn
i=1
aixi b;
xi 2 f0; 1; 2g; i = 1; : : : ; n:
(1)
For the instance under the consideration, the model is of the form:
min f = 14x1 +13x2 +10x3 +12x4
s.t. 10x1 +7x2 +4x3 +3x4 12
xi 2 f0; 1; 2g ; i = 1; : : : ; 4:
The problem is similar to the one considered in Chapter 7, but there are two points of di§erence:
the direction of optimisation (minimisation) and the sign in the inequality constraint ().
2.1 For the minimisation problem (1), the branch and bound algorithm needs the formula for
calculating lower bounds for each node of the search tree.
Suppose generators are numbered so that(2)
Consider a node of the search tree with the Örst k variables Öxed,
x1 = h1; : : : ; xk = hk;
and the remaining variables xk+1, . . . , xn non-Öxed. The task is to prove the following
formula for calculating a lower bound for that node:
(3)
You can use the arguments similar to those presented in Chapter 7 for calculating upper
bounds for the max-problem. [7 marks]
2
2.2 Suppose in problem (1) all data are integer and consider the following expressions derived from
(3):
Select all correct options. (Penalty [-1] for each incorrect answer ).
LB0
is not a true lower bound for some instances
LB0
is a correct lower bound for all instances
LB00 is not a true lower bound for some instances
LB00 is a correct lower bound for all instances
Both formulae, LB0 and LB00, are correct lower bounds for all instances and it does not
matter which one is used
Both formulae, LB0 and LB00, are correct lower bounds for all instances, but LB0
should
be preferred
Both formulae, LB0 and LB00, are correct lower bounds for all instances, but LB00 should
be preferred
[6 marks]
2.3 Find an optimal solution by the branch-and-bound algorithm. Present the search tree. Use
the depth-Örst strategy, selecting each time the most promising node among all child nodes
of the same parent node. Number the nodes of the tree in the order they are obtained. State
the optimal solution and its cost. [15 marks]