2018-2019

3. Consider the example of a blending manufacturer who is producing feed mix for animals.
In this example, the blend contains two active ingredients out of three alternative ones,
and a filler to provide bulk. Table Q1 below provides the minimum quantity of each
nutrient that must be present at the feed.
Table Q1: Minimum quantity (g) of each feed nutrient
Nutrient A B C D
g 80 60 30 20

A blend product can be approved provided that the minimum quantity is satisfied for at
least three of the four nutrients.
The ingredients and filler have the following nutrient values and costs as shown in Table
Q2:
Table Q2: Nutrient values and cost of each part
𝒈 𝑵𝒖𝒕𝒓𝒊𝒆𝒏𝒕
A B C D Cost/kg
𝒌𝒈 𝑰𝒏𝒈𝒓𝒆𝒅𝒊𝒆𝒏𝒕

Ingredient 1 100 70 50 20 40

Ingredient 2 300 120 10 0 50

Ingredient 3 200 90 30 10 30

Filler 0 0 0 0 3
The problem is to determine the amount of active ingredients in one kg of feed mix at
minimum cost. Formulate the above problem as an MILP model by answering all parts of
the following:
(a) optimisation variables (binary and continuous)
(b) objective function by minimising the total cost
(c) mathematical constraints for the minimum quantity constraints, material balance and
nutrient constraints
(d) logical constraints for selecting 2 out of 3 alternative ingredients.

Sets:
i set of ingredients
j set of nutrients
Parameters
𝑞! minimum quantity of nutrient j of the final feed mix
𝑉"! nutrient j values of ingredient i
𝑐" cost of ingredient i
Positive Variables
𝑥" the amount (kg) of ingredient i in one kg of feed
Binary Variables
𝑧! 1 if nutrient j is selected; 0 otherwise
𝐸" 1 if ingredient i is selected; 0 otherwise

CENG0023 1
Equations
Material balance: The summation of the selected ingredient should be equal to feed
amount(1kg)
' 𝑥" = 1
"

Nutrient constraint: Minimum quantity should be satisfied for at least three of the four
nutrients.
' 𝑧! ≥ 3
!

Minimum quantity constraint: Minimum quantity constraint should be forced if nutrient j is

selected.
' 𝑉"! 𝑥" ≥ 𝑞! ∙ 𝑧! ∀𝑗
"

Objective function
min ' 𝑐" 𝑥"
"

Logical constraints:
i) select two ingredients
' 𝐸" = 2
"

(or ∑" 𝐸" = 3 𝑎𝑛𝑑 𝐸" = 1 𝑓𝑜𝑟 𝑖 = 𝑓𝑖𝑙𝑙𝑒𝑟)

ii) if ingredient i is not selected, then the corresponding ingredient amount, 𝑥" ,
should be forced to zero

𝑥" ≤ 𝐸" ∀𝑖

CENG0023 2
4. Answer all parts of the following:
(a) Let Xt be a binary variable denoting whether or not production takes place over
time period t. If the product starts being manufactured at period t (i.e. Xt=1 and Xt-
1 =0) then production should be forced to continue for the next m-1 periods, thus
keeping an uninterrupted production of at least m time periods (i.e. t, t+1,…, t+m-
1). Formulate the above statement mathematically as a mixed integer linear
constraint.

m -1

å
q
X
=1
t +q ³ (m - 1)( X t - X t -1 )
The above constraint is active only if Xt=1 and Xt-1=0. In this case, all Xt variablers
involved in the summation are forced to take the value of one. For all other
combinations of Xt and Xt-1, the above constraint is inactive.

(b) There are M power stations committed to satisfy the electricity demand, D. The
fuel cost function of each power station can be described by a linear function of
output of power station j, Pj (MW), as: F j = A j + B j Pj where Aj and Bj are known
parameters. Each power station j is characterised by k allowed power ranges
( Pjkmin , Pjkmax ) . So, each power station either operation in one of the k power ranges
otherwise the output of that power station should be forced to the value of zero.

Assume that there is no power loss. Formulate the above problem as a mixed integer
linear programming (MILP) model without solving it so as to select the optimal
operation of power stations by specifying
(i) optimisation variables (binary and continuous)
(ii) objective function by minimising total fuel cost
(iii) mathematical constraints for power output for each station if operating within
a given range
(iv) mathematical constraint to satisfy electricity demand.

Each station j is characterised by k (here, equal to 2) allowed power ranges ( Pjkmin , Pjkmax ) . The
following variables are introduced:
Wj; 1 if power station j operates; 0 otherwise.
Yjk: 1 if power station j is operates in range k; 0 otherwise
Pj: output of power station j
Zjk: output of power station j is operates in range k (i.e. if Yjk=1 then Zjk=Pj)

The resulting mathematical model will be:

Objective Function

CENG0023 3
Min åF
j
j

where
𝐹! = 500 𝑊! + 10 𝑃! "j

Subject to

Power allocation constraints

∑# 𝑌!# ≤ 𝑊! "j

Each power station should operate within one range, if active.

If power station j operates in range k, then Zjk will be equal to Pj, otherwise it is forced to
zero.
Pj = å Z jk "j
k

PjkminYjk £ Z jk £ PjkmaxYjk "j, k

Demand constraints
åP = D
j
j

where D is given electricity demand

CENG0023 4
 2019-2020

3. The Research and Development department of a company has developed three new
products (i = A, B, C) to be manufactured at three possible plants (j = 1, 2, 3). The
following table Q1 provides i) the production times at each plant j for each unit of
product i (PTij), ii) the production times available per week at each plant j (ATj), iii) the
per-unit profit of each product i (pi), and the sales potential (demand) of each product
i (Di):

Table Q1: Input data

Production time for each unit Production time
Plant\Product A B C available per week
Plant 1 3 hours 4 hours 2 hours 60 hours
Plant 2 4 hours 6 hours 2 hours 80 hours
Plant 3 2 hours 5 hours 3 hours 70 hours
Unit profit 3000 4000 2000 (£)
Sales potential 6 4 8 (units per week)

The company needs to determine which one of the three plants should be chosen to be
the sole producer of the new products, what products are manufactured at the selected
plant as well as the production rates of the chosen products so as to maximise the total
profit. Formulate the above problem as a mixed integer linear programming (MILP
)model by answering all parts of the following:

(e) What are the optimisation variables (binary and continuous)

[6]
(f) Define the objective function which maximises the total profit
[4]
(g)Provide the mathematical constraints (satisfying the production, plant and sales
aspects)
[12]
(h)Give the logical restrictions.
[3]

CENG0023 5
a) Introduce the Indices
i = product: Product1, Product2, and Product3
j = factory: Factory1, and Factory3

Introduce the following variables:

Xij: production rate of product i in factory j (units/week); all constrained to be
nonnegative
Yij: 1 if product i is chosen to be manufactured at plant j; 0 otherwise
Zj: 1 if plant j is selected to manufacture the products; 0 otherwise

b) Objective function
The objective is to maximise the total profit (total profit is calculated by the
production rate multiplied by the corresponding unit profit, pi):
𝑚𝑎𝑥 𝑧 = ' ' 𝑝" 𝑋"!
" !

c) Model constraints
Sales constraint: åX j
ij £ Di "i
The total production rate of a product cannot exceed the sales potential of the
product

Production constraint: X ij £ M × Yij "i, j

where M is a large number. If a product is not produced at a factory (i.e. Yij=0), its
production rate at the factory should be zero; otherwise, it should be limited by an
upper bound.
Allocation constraints: å
Yij £ card (i) × Z j "j
i
If a factory is not chosen for production, no product will be allocated to that factory.
Here, Card(i) is the cardinality of set i, i.e., the total number of products considered.

Time constraint: å PT X
i
ij ij £ AT j × Z j "j
The total production time of a factory cannot exceed the maximum capacity of the
factory, if the factory is chosen for production.

d) Logical constraint: only one plant should be selected åZ

j
j =1

CENG0023 6
4. Answer all parts of the following:

a) A blending company can purchase up to five ingredients: A, B, C, D and E. Formulate

the following cases as mixed integer linear programming constraints:
i) Select up to four out of five ingredients.
ii) Select at least three ingredients.
iii) If ingredient E is selected then A or B should be chosen.
iv) Ingredient A cannot be chosen if ingredient B is chosen.
v) If either A or B is selected then at least one of C,D and E must be.
[15]

a)
Introduce binary variable Yi to indicate whether ingredient i is selected
5
i) åY
i =1
i £4
5
ii) åY ³ 3
i =1
i

iii) YE £ YA + YB
iv) YA ≤ 1− YB
iv)
𝑌$ + 𝑌% ≤ 2 𝑍
𝑌& + 𝑌' + 𝑌( ≥ 𝑍

b) Consider a regression optimisation problem, which aims to minimise the absolute

value of the difference between the experimental value (Y) and the value predicted
by regression function, Y . Formulate the above problem as a linear programming by
specifying the following:

i) optimisation variables
[2]
ii) objective function by minimising absolute value
[2]
iii) mathematical constraints
[6]
Define D (positive) as the absolute deviation between the experimental value, Y, and
the predicted value, 𝑌J:
𝐷 ≡ |𝑌 − 𝑌J|
Given that Di is minimised in the objective function, we can obtain its correct value
by:
𝐷 ≥ 𝑌" − 𝑌J
𝐷 ≥ 𝑌J − 𝑌
By miminising variable D:
Min D

CENG0023 7
 2023-2024

1. Answer all parts of the following:

a) Give three process design objective functions for more sustainable design or
operation of chemical processes. Illustrate with examples. [6]

Minimise waste product, minimise CO2 production, minimise costs

(economics one of three arms of sustainability with environmental and
social). Examples from minimising CO2 from furnace or maximising CO2
recovery for storage or utilisation.

b) What is meant by a convex function and why is convexity important? [3]

Line joining two points on the curve of the function will always lie above the function
itself. May be multiple optima so Newton type methods will find local optima and not
necessarily global optimum.

c) Perform one iteration of a Newton-based method without line search for the
following problem starting from the point [1 1]T
Minimise (x1 – 6) 2 + (x2– 2) 2 + 10 [6]

(see lecture - NLP Examples1 – problem 4)

CENG0023 8
CENG0023 9
2. Answer all parts of the following:

….

e) Determine the minimum of the following objective function

x2 + y2 + z2
subject to the following constraint
x + 2y –z = 1
How would you determine whether this was the true optimum? [6]

Make use of the KKT conditions to obtain the optimal solution of the constrained NLP.

min f = x2 + y2 + z2
s.t. x + 2y –z = 1

L = x2 + y2 + z2 + l(x + 2y –z - 1)

ÑxL = 2x + l = 0 x = -l/2
ÑyL = 2y + 2l = 0 y = -l
ÑzL = 2z - l = 0 z = l/2

ÑlL = x + 2y –z = 1 Þ -l/2 - 2 l -l/2 = 1 Þ l = -1/3

x = 1/6, y = 1/3, z = -1/6

check that all ÑL are zero, constraint is satisfied, so this is a Kuhn-Tucker point

Also, f(x) convex, h(x) linear à convex problem.

CENG0023 10
 3. Answer all parts of the following:

a) Describe main steps of the Simplex method for the solution of linear programs.
[5]
a) Simplex method
The main steps of the Simplex algorithm have as follows:
1. Bring the model in its canonical form through the introduction of slack variables
2. Find the initial basic solution vertex
3. Select new basis through pivoting (pivot column: max positive coefficient; pivot row:
min positive ratio)
4. Perform Gauss-Jordan elimination to transform the equations based on the new
basis
5. Iterate until all coefficients in the row of objective are non-positive

b) Solve the following Linear Program (LP) by using the Simplex method with initial
feasible solution X1 = X2 = 0.

𝑀𝑖𝑛 𝑧 = −3𝑋) − 4𝑋*

𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜
6𝑋) + 2𝑋* ≤ 12
5𝑋) + 10𝑋* ≤ 50
where X1 and X2 are positive continuous variables.
[10]
b) Solve following LP by Simplex
𝑀𝑖𝑛 𝑧 = −3𝑋! − 4𝑋"
𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜
6𝑋) + 2𝑋* ≤ 12
5𝑋) + 10𝑋* ≤ 50
Solution: Introduce slack variables x3 and x4; so we have:
6x1 + 2 x2 + x3 = 12
5x1 + 10 x2 + x4 = 50
f + 3x1 + 4 x2 = 0

X1 X2 X3 X4 f b b/xi
X3 6 2 1 0 0 12 12/2
X4 5 (10) 0 1 0 50 50/10
3 4 0 0 1 0
Pivot: column 2; row2

Row 2 = (1/10) Row 2; Row 1 = Row 1 – (2) Row 2; Row 3 = Row 3 – (4) Row 2

CENG0023 11
 X1 X2 X3 X4 f b b/xi
X3 (5) 0 1 -0.2 0 2 2/5
X2 0.5 1 0 0.1 0 5 5/0.5
1 0 0 -0.4 1 -20
Pivot: column 1; row1

Row 1 = (1/5) Row 1; Row 2 = Row 2 – (0.5) Row 1; Row 3 = Row 3 – (1) Row 1
X1 X2 X3 X4 f b b/xi
X1 1 0 0.2 -0.04 0 0.4
X2 0 1 -0.1 0.08 0 4.8
0 0 -0.2 -0.36 1 -20.4

The procedure terminates because no Xi coefficients in the last row are positive.
Answer: f = – 20.4 at X1 = 0.4 , X2 = 4.8.

CENG0023 12
 c) The aim is to fit the ‘best’ function ( Y = AX 2 + BX + C ) to a given set of I
experimental data points [Xi, Yi], where i = 1,…I. Based on the deviations
between the experimental value (Y) and the value predicted by the above
quadratic relation, Y , formulate the following two cases as linear programming
models:
i) Minimise the sum of the absolute value of the deviations. [7]
ii) Minimise the maximum absolute value of the deviations. [3]

Let’s use Yi as the prediction given by: Yi = AXi2 + BXi + C

Define Di as the absolute deviation between the experimental value, Yi, and the
predicted value, Yi :
V+ |
𝐷" ≡ |𝑌" − 𝑌
In case i), the objective is to minimise the summation of the absolute values of the
deviations:
Min åD i
i

Given that Di is minimised in the objective function, we can obtain its correct value
by:
Di ³ Yi - Yi
Di ³ Yi - Yi
In case ii), the objective is to minimise the maximum value of the absolute deviations.
First, we introduce an extra continuous variable, Z, which will be equal to the
maximum Di. This can be achieved by:
Z ³ Di "i
while the objective function for case ii) will be:
Min Z

CENG0023 13
 4. Consider a company that 3 productions plants (i = P1, P2, P3) from which a
single product is distributed to 3 customers (j = M1, M2, M3). The following table
Q1 provides i) distribution unit cost £ ton-1) from plant i to customer j (Cij), ii)
maximum production rate (ton day-1) for each plant i (Ai) and iii) demand rate (ton
day-1) for each customer j (Dj):

Table Q1: Input data

Distribution unit cost (£ ton-1) Maximum Plant
production rate
Plant\Customer M1 M2 M3 (ton day-1)
P1 25 60 75 20
P2 20 50 85 22
P2 35 45 80 15

Customer demand 14 12 8
rate (ton day-1)

The cost of production for plant P1 is 40 £ ton-1 for total production rate less than
10 ton day-1; 30 £ ton-1 for total production rate greater than 10 ton day-1. The
production costs of plants P2 and P3 are uniform at 35 £ ton-1 and 25 £ ton-1
respectively.

The company needs to determine plant production rates and distribution policy
so as to minimise total cost. Formulate the above problem as a mixed integer
linear programming (MILP) model by specifying:

(a) optimisation variables (binary/integer and continuous) [4]

(b) objective function which minimises the total cost [4]
(c) mathematical constraints (satisfying production and demand aspects) [6]
(d) logical constraints for production outputs [6]

If there is a requirement that production can take place at most at two plants,
describe new variables and constraints required to be added to the above model.
[5]
(see Mock test during last lecture)

Each production plant i is characterised by k rate regions (here, equal to 2 for plant P1 or 1 for
,"- ,./
plants P2/P3) allowed productions rate ranges (𝑃"# , 𝑃"# ). The following notation is
introduced:
Sets
i: production plants (P1, P2, P3)
j: customers (M1, M2, M3)

Parameters
Ai: maximum production rate for plant i
Dj: demand rate for customer j
Cij: unit distribution cost from plant i to customer j

CENG0023 14
CPik: unit production cost if plant i is operating in rate region k

Binary variables
Yjk: 1 if production plant i is operates in range k; 0 otherwise
Pj: output of production plant i

Positive continuous variables

Ojk: output of production plant i if operating in range k (i.e. if Yjk=1 then Ojk=Pj)
Xij: product amount distributed from production plant i to customer j

min 𝑍 = ' ' 𝐶𝑃"# 𝑂"# + ' ' 𝐶"! 𝑋"!

" # " !
The resulting mathematical model will be:

Objective Function
min 𝑍 = ' ' 𝐶𝑃"# 𝑂"# + ' ' 𝐶"! 𝑋"!
" # " !

Subject to
Demand constraints
' 𝑋"! ≥ 𝐷! ∀𝑗
"

where Dj is given demand for customer

Production constraints:
Production for each plant should be equal to the amount distributed to all customers, and
must be less that maximum production rate.
𝑃" = ' 𝑋"! ∀𝑖
!
𝑃" ≤ 𝐴" ∀𝑖

Logical constraints
Each production plant should operate within one rate range, if active
' 𝑌"# ≤ 1 ∀𝑖
#

If production plant i operates in range k, then Oik will be equal to Pi, otherwise it is forced to
zero.
𝑃" = ' 𝑂"# ∀𝑖
#

and
,"- ,"-
𝑃"# 𝑌"# ≤ 𝑂"# ≤ 𝑃"# 𝑌"# ∀𝑖, 𝑘

CENG0023 15
Extra requiremet: if at most two plants can operate, we need to introduce additional binary
variable
Ei: 1 if production plant is selected; 0 otherwise

together with the following constraints

No operating rate region can be selected if plant is not active (ie. if Ei=0 then all relevant
Yik=0)
' 𝑌"# ≤ 𝐸" ∀𝑖
#

and at most two plants can be selected:

' 𝐸" ≤ 2
"

CENG0023 16