MAST30013 – Techniques in Operations Research

Semester 1, 2024

Group Project

Submissions:Project reports are to be submitted before the (strict) due date: 11:59pm

Friday of Week 11 (17 May, 2024). A complete submission will consist of aLaTex typeset

report in pdf form and the Matlab files of your implementation.

Groups:must be composed of aminimum of 3and amaximum of 4members. It is

your responsibility to talk to your classmates and create/find a group, as early as possible

in the semester.

Evaluation:

Reporting:You should present a coherent and self-contained report presenting your

algorithms and results for the questions below. Each student should contributeat least

5 pagesto the report, and every page should name (as a footnote) the person responsible

for it.

Presentation:In the last week of semester, groups will present their work in10 minutes

+ 3 minutesfor questions during the usual lecture times, and the tutorials. You are

NOT expected to explain the problem in detail during the presentation. Instead, focus

on the innovative aspects of your methods and theory. Which solution algorithm did you

implement? What conclusions did you get? All group members are expected to speak in

order to get an oral mark.

Report Structure:

Introduction (Motivation, applications)

Background (Mathematical preliminaries)

Theory (Answers to all the tasks below)

Algorithms (Pseudo-code and descriptions)

Experimental setup (What instances are you testing and how will you evaluate the results?

Which algorithms will you compare and how? What hardware are you using?)

Experimental results (Graphs and tables)

Discussion and results (What do you conclude?)

Project Description

A logistics company plans to install a parcel locker in the downtown area to cover the

delivery demand ofNresidential buildings. Letr

i

∈R

2

fori= 1,2,...,Ndenote the

locations of these buildings andx∈R

2

denote the location of the parcel locker. Let

||a−b||denote the Euclidean distance betweenaandb. The “undesirability”, which

represents the unwillingness of the residents in buildingiusing the parcel locker, is given

1

by

u

i

(x) =







c

i

if||x−r

i

||≤δ,

c

i

δ

2

||x−r

i

||

2

otherwise.

Formally, we have a nonlinear program:

min

x∈R

2

N

∑

i=1

u

i

(x).

Tasks:

1. Prove that the unconstrained problem, as formulated above, is NOT C

1

but is convex.

Illustrate an example consisting of three buildings in the plane by drawing the lines

consisting of all points at which the problem is not differentiable.

2. Remodel the problem as a constrained optimisation problem with a smooth objective

function. Prove that the problem is still convex. You should explain each constraint

and variable.

3. Derive the KKT conditions for the model in Part 2.

4. Implement an algorithm for solving your model in Part 3. Do a computational study

(different initial conditions, parameter settings, etc.) for instances of different values

ofNand various random sets ofNpoints. Compare your algorithm with other

algorithms or pre-existing optimisation functions in Matlab.

Important Notes

•You will be marked on the quality of your report. Make sure it is self contained and

follows the structure of a scientific report.

•It is the group’s responsibility to ensure that everyone contributes their fair share to

the project.

•It is recommended that members of the group share a Dropbox folder for their work

or use Overleaf. This is so that all group members can have access to all parts of the

project at any time.

•This project contains an extensive programming component. It is assumed that all

students are able to program in Matlab. The lecturer willNOTassist in issues

relating to the debugging of code.

•Students may research ideas on the web, but full credit to the relevant authors must

be given if the students use any of these ideas. Code may NOT be copied from existing

sources (except for code, eg., BFGS etc., provided by the lecturer). Collaboration

between groups is NOT allowed.

•All code must be in Matlab. Code will not be marked directly, but marks may be

deducted for messy code or code that is not well commented. Code must be in a

form so that the lecturer can easily test your algorithm on an independent set of

instances.

2