Locating IMEXs in Melbourne

This assignment discusses the process of locating IMEXs in Melbourne using different methods and algorithms. It includes the analysis of the functions, formulation of linear programs, and code for computing optimal solutions. The assignment also explores the extensions and ways to make the model more realistic.

ECE3093 Assignment 2: Melbourne 2050
April 2019
Name: ________________________ Student ID: _________________
Electronic submission of this assignment is due on Moodle on Monday 6 May 2019. You are
required to submit this file as pdf, and the source code (Matlab script). Note: you may insert scans
or photos of your handwritten notes for any of the answers requiring mathematics.
1. Locating a single IMEX in the plane
a) How many local & global minima does this function have? (Give reasons) [2 marks]
The function has one local minima where the value of the objective function is less than all the
nearby points which are all the (xi,yi) points of n= 99 locations in the Melbourne city. Also, the
function has one global minima which is smaller than all the feasible points of the objective
function.
b) Formula for calculating an optimal IMEX location [2 marks]
The formula for calculating an optimal IMEX position is to apply the method of least square.
The objective function is
Min f (u , v ) = ∑
i=1
n
qi( ( u−xi )2 + ( v − yi )2)
Now, where f (u , v ) is minimum there the gradient is zero.
Hence, ∇f (u , v ) = [0
0 ] (1)
Now, putting the (xi,yi) values and then solving equation (1) gives the Global optimal
solution.
c) Global Optimal solution: [2 marks]
pg. 1 ECE3093 Assignment 2 2019

x-coordinate y-coordinate
71 65
f = 18,26,9
91
-3 17 37 57 77 97 117 137 157
0
20
40
60
80
100
120
Single Centre
2. Locating a single IMEX using Manhattan distances
g ( u , v )=∑
i=1
n
qi (|u−xi|+|v − yi|)
a) Formulate min
u , v
g(u , v ) as a linear program [5 marks] .
Minimize g(u,v) = ∑
i=1
n
qi (|u−xi|+|v − yi|)
Now, as u,v >=0 hence, |u−xi|=|u|−¿ xi∨¿ and ¿ v – yi| = |v|−| yi|
Hence, the LP problem becomes
Minimize, ∑
i=1
n
qi∗u+qi∗v−∑
i=1
n
(q ¿¿ i∗xi +qi∗yi) ¿
Subjected to,
pg. 2 Solution to ECE3093 Assignment 2 2019

u, v are integers
u>= 0
v>= 0
b) Write down the dual of this linear program. [5 marks]
Now, let the dual variables are μ and λ for the primal problem defined earlier.
Hence, Dual problem will be
Maximize, ∑
i=1
n
qi∗ (−μ ) + qi∗(−λ)−∑
i=1
n
(q ¿¿ i∗xi +qi∗yi) ¿
Subject to Constraints,
μ >= 0
λ >= 0
c) Solution found from solving the linear program [5 marks]
pg. 3 Solution to ECE3093 Assignment 2 2019

x-
coordinate
y-
coordinate
70 68
g = 52,5
-3 17 37 57 77 97 117 137
0
20
40
60
80
100
120
Single Centre
d) Bonus Question: Direct method for computing the primal & dual solution [5 marks]
Now, without solving the primal or dual problem to find the optimal u and v, it can be seen that
from the data the number of occurrence of xi = 70 and yi = 68 in the location co-ordinates is
the maximum. Hence, the optimal co-ordinates which will minimize the straight line distances
between the locations need to be those maximum frequency points. Hence, the optimal
solution by direct investigation is (u,v) = (70,68)
pg. 4 Solution to ECE3093 Assignment 2 2019

3. Locating multiple IMEXs in the plane
min
u , v ,k
h ( u , v , k )=∑
i=1
n
qi (|xi−uk (i )|+| yi−vk ( i )|) such that k (i ) ∈ {1 , … , p } for i=1 , … , n ( p=5 ¿
a) Code for computing best allocation vector and locations, starting with random k [5 marks]
Pseudocode for best allocation vector and locations:
Load qi,xi,yi
k = 1;
while k<=5
For i=1:length(qi)
h(i) = q(i)*(abs((x(i) – u(k(i)) + abs(y(i) – v(k(i)))
end For
h = sum(h(i)) % objective function
intcon = [];
A = [1,1]
b = [0,0]
sol(i) = intlinprog(h,intcon,A,b) % solving linear programming problem
kval(i) = k
k = k+1
end While
best_sol = min(sol)
if sol(i) == best_sol
k = k(i)
end
b) Analysis of algorithm [4 marks]
In the above algorithm the optimal u, v and k are found for k IMEX where k =5 by taking
random k and evaluating the objective function and then solving the values of u and v by
linear programming. Then k is incremented and the process is repeated and the best k for
which minimum of h(u,v,k) is obtained is chosen for an IMEX. This problem is a convex
optimization problem as the minimization is perform on a convex objective function and the
feasible set is a convex set. If different k value is chosen out of the range [1,5] then the
algorithm will not converge or optimized solution can’t be found, otherwise a local optimized
pg. 5 Solution to ECE3093 Assignment 2 2019

solution can be found.
c) Solution of the 5 IMEX problem [5 marks]
1st
IMEX
2nd
IMEX
3rd
IMEX
4th
IMEX
5th
IMEX
61 76 70 66 75
73 65 69 68 75
h = 50,9
42
allocati
on
4
1
5
5
5
3
5
2
2
3
3
3
2
1
5
4
2
4
2
3
3
5
pg. 6 Solution to ECE3093 Assignment 2 2019

5
3
3
1
4
5
2
5
2
5
2
4
4
3
3
3
2
3
5
1
1
2
2
2
5
4
2
1
4
5
3
1
5
2
5
2
4
3
5
5
5
3
5
3
4
1
2
pg. 7 Solution to ECE3093 Assignment 2 2019

3
3
5
2
2
4
5
2
2
3
3
3
5
1
2
1
3
5
3
2
1
3
4
5
5
1
3
5
1
5
pg. 8 Solution to ECE3093 Assignment 2 2019

-3 17 37 57 77 97 117 137 157
0
20
40
60
80
100
120
5 IMEX solution
4. The discrete IMEX location problem
a) Analysis of enumeration approach [2 marks]
pg. 9 Solution to ECE3093 Assignment 2 2019

b) Integer Linear Programming Formulation [5 marks]
c) Code corresponding to the above formulation [0 marks]
d) Solution [5 marks]
1st IMEX 2nd IMEX 3rd IMEX 4th IMEX 5th IMEX
k 1 2 4 23 16
q 232 303 267 149 314
u 67 39 80 47 45
v 54 111 46 96 66
h = 76,290
Allocation (k) = [ 4 1 2 5 5 3 4 2 3 3
5 5 3 3 1 4 5 2 5 2 5 2
4 4 3 3 3 2 3 5 1 1 2 2
pg. 10 Solution to ECE3093 Assignment 2 2019

2 5 4 2 1 4 5 3 1 5 2 5
2 4 3 5 5 5 3 5 3 4 1 2
3 3 5 2 2 4 5 2 2 3 3 3
5 1 2 1 3 5 3 2 1 3 4 5
5 1 3 5 1 5]
5. Extensions
a) Some ways this model could be made more realistic [3 marks]
pg. 11 Solution to ECE3093 Assignment 2 2019

pg. 12 Solution to ECE3093 Assignment 2 2019