Optimization Modelling And Decision Analysis

Page 1 of 1

SIT399 Summative Assessment Task 3 Trimester 1, 2020

Due 11:30PM Friday May 29th 2020

Special Instructions

This assessment task is for students to demonstrate their ability to understand an optimisation prob-

lem, be able to formulate a mathematical programming model, and to apply a commercial software

to solve the mathematical programming problem.

The assessment is to be submitted online via Dropbox folder on or before the due date. The full mark

for this Assessment Task is 15, and is worth 15% of the total mark for the unit.

Problem description

You have learned the Asymmetric Travelling Salesman Problem in Integer Programming, where you

were taught an exponential-size formulation. What you may or may not know is that there is actually

a polynomial-size formulation.

It uses a continuous variable for each vertex on the graph as a time-stamp. Now, if we visit City

j immediately after City i, then the time-stamp of City j, uj should be at least ui + 1, for ui the

time-stamp of City i. With the u-variables, and the original x-variables, we are able to model the

Asymmetric Travelling Salesman Problem with polynomially many variables and constraints.

The cool thing about polynomial-size formulation is that it can be

Now, for this task, you are to find out what the polynomial-size formulation is, understand how it

works, model it using CPLEX, and solve the data instance provided for this assignment (see Excel

file: data.xlsx).

In specific, you are required to perform the following tasks and to produce a report that is no longer

than 8 pages.

1. Research the web for references of the polynomial-size formulation for ATSP, it can be lecture

notes, papers, or videos. Provide the URL (1 mark)

2. Write down the entire polynomial-size formulation for ATSP (3 marks)

3. Explain the constraints and the variables, and how the polynomially many constraints work in

eliminating subtours, using an example (5 marks)

4. Code up the model in CPLEX OPL modelling language (5 marks)

5. Solve the data instance provided in the assignment folder and write down the solution (1 mark)

Your report should be typed up in Word or LaTeX but submitted as a single PDF. The

OPL model should be submitted as a separate file, but take a screen shot or copy-and-

paste and include it in the report.