MAST30013 – Techniques in Operations Research
Semester 1, 2023
Group Project
Submissions: Solutions are to be submitted before the (strict) due date: 5pm Friday of
Week 11. A complete submission will consist of a LaTex typeset report in pdf form and
the Matlab files of your implementation.
Evaluation:
Reporting: You should present a coherent and self-contained report presenting your
algorithms and results for the questions below. Each student should contribute at least 5
pages to the report, and every page should name (as a footnote) the person responsible
for it.
Presentation: In the last week of class, groups will present their work in 5 minutes +
2 minutes for questions during the usual lecture times, and possibly one of 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 Tasks 1-5)
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
We are given N points y1, ..., yN on the plane and a convex and closed set X ⊂ R2. Our
objective is to find a point x ∈ X for which the distance to the nearest point yi is the
largest possible.
Tasks:
1. Model this problem as a constrained nonlinear “maxi-min” problem and then convert
the program to a “mini-max” problem.
1
2. For the mini-max version, characterise the set of points for which the objective func-
tion is NOT differentiable when X = R2. Illustrate the characterisation on the
following example: y1 = (0, 0), y2 = (1, 0), y3 = (0, 2), y4 = (4, 4). Include a figure
showing all non-differentiable points.
3. Let X = {(x1, x2) ∈ R2 : x2 ≥ 0, x21 + x22 ≤ 1}. For this X, rewrite the mini-max
problem as a nonlinear program with a smooth objective.
4. Write out all the KKT conditions for the program in (3). Explain why we can
essentially ignore points for which the constraints are not smooth.
5. Bonus question: Provide a geometric interpretation of the points that satisfy the
KKT conditions. (Hint: try X = R2 if that simplifies things).
6. Implement an algorithm for solving your model in (3). Do a computational study
(different initial solutions, parameter settings, etc.) for instances of different values of
N and various random sets of N points. Note, X stay fixed as defined. 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 will not assist 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 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.