FIND A SOLUTION AT Academic Writers Bay

Page 1 of 3

SIT399 Summative Assessment Task 3

Report

Trimester 1, 2021

Due 11:30pm May 30th, 2021

1 Problem description

Consider the combinatorial optimization problem described as below.

Let D = (V; A) be a directed graph with V the set of vertices and A the set of arcs, i.e., A =

f(i; j) j i; j 2 Vg. On each arc a 2 A, there is a reward ra associated with it. The optimization

problem is to form one or more cycles using the arcs, with each arc used in no more than one cycle.

The cardinality of the cycle(s) cannot be more than a given number K. The objective is to maximize

the sum of rewards for the arcs used in the cycles.

The major differences between this problem and the well-known Asymmetric Travelling Salesman

Problem (ATSP) are as follows.

1. A solution that contains more than one subtour” is considered feasible, however, the size of

each subtour must be no more than K vertices.

2. A feasible solution does not necessarily have to involve all vertices in V.

3. The objective is to maximize total reward of arcs used instead of to minimize total cost of arcs

used.

Let:

• xi;j 2 f0; 1g be a binary variable with xi;j = 1 indicating Arc (i; j) 2 A is used in the solution

and xi;j = 0 otherwise;

• PK be the set of all simple paths with exactly K vertices; and

• τ = (i1; : : : ; iK) 2 PK be an arbitrary simple path with exactly K vertices, i.e., the arcs in the

path are: (i1; i2); (i2; i3); : : : ; (iK-1; iK)

An integer linear programming (ILP) model is given as below.

Model 1

max

X

(i;j)2A

rijxij

(1)

s.t. X

(i;j)2A

xij ≤ 1; 8i 2 V (2)

X

(j;i)2A

xji = X

(i;j)2A

xij; 8i 2 V (3)

xi1;i2 + xi2;i3 + · · · + xiK-1;iK – xiK;i1 ≤ K – 2; 8(i1; : : : ; iK) 2 PK (4)

xij 2 f0; 1g; 8(i; j) 2 A: (5)

SIT399 Summative Assessment 3 Trimester 1 2021 Page 2 of 3

2 Part I

Use CPLEX OPL to model and solve the problem with the data file provided. Upload the model file,

data file, and solutions to designated Assignment Dropbox on CloudDeakin.

a) The model to capture the objective function as well as Constraints (2), (3), and (5), to produce

a solution successfully and accurately.

Level of Task = Pass

Mark = 1 if the task is successfully completed and submitted, 0 otherwise

Weight = 10

b) (i) In addition to (a) above, the model also captures Constraints (4)

Level of Task = Distinction

Mark = 1 if the task is successfully completed and submitted, 0 otherwise

Weight = 5

(ii) Solutions are produced successfully and accurately for each of the following two cases:

K = 3, and K = 4.

Level of Task = Credit

Mark = 1 if the task is successfully completed and submitted, 0 otherwise

Weight = 5

3 Part II

Produce a video (max 5 mins in total for all components of Part II listed below) to explain:

(a-i) Constraint (2)

Level of Task = Pass

Mark = 1 if the task is successfully completed and submitted, 0 otherwise

Weight = 5

(a-ii) Constraint (3)

Level of Task = Pass

Mark = 1 if the task is successfully completed and submitted, 0 otherwise

Weight = 5

(a-iii) Constraint (4)

Level of Task = Distinction

Mark = 1 if the task is successfully completed and submitted, 0 otherwise

Weight = 5

SIT399 Summative Assessment 3 Trimester 1 2021 Page 3 of 3

(b) The solution(s) you have obtained in Part I

Level of Task = Credit

Mark = 1 if the task is successfully completed and submitted, 0 otherwise

Weight = 5

4 Part III

The total weight of this task is 20 and the weights are the same as the marks indicated for each

component of the task.

(a) Model 1 is not scalable for larger K. Explain why in no more than 100 words.

Level of Task = High Distinction

Mark = 5

(b) An alternative way to model the problem is to clone the digraph D into jVj copies. (That is, if

there are 50 vertices, then there will be 50 copies of the same directed graph).

Now, using a new binary variable x‘ ij 2 f0; 1g with x‘ ij = 1 to represent Arc (i; j) is part of the

cycle in the ‘th copy of D, formulate an integer linear programming model that solves the same

problem stated in this assessment with only polynomially many constraints.

Level of Task = High Distinction

Mark = 12

(c) Is the following statement true? Explain your answer in no more than 100 words.

Each copy of the digraph will contain no more than 1 cycle.

Level of Task = High Distinction

Mark = 3

- Assignment status: Already Solved By Our Experts
*(USA, AUS, UK & CA PhD. Writers)***CLICK HERE TO GET A PROFESSIONAL WRITER TO WORK ON THIS PAPER AND OTHER SIMILAR PAPERS, GET A NON PLAGIARIZED PAPER FROM OUR EXPERTS**

QUALITY: 100% ORIGINAL PAPER – **NO PLAGIARISM** – CUSTOM PAPER