# SIT399 Summative Assessment

FIND A SOLUTION AT Academic Writers Bay

Page 1 of 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.
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)
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.
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)
Mark = 1 if the task is successfully completed and submitted, 0 otherwise
Weight = 5
(a-ii) Constraint (3)
Mark = 1 if the task is successfully completed and submitted, 0 otherwise
Weight = 5
(a-iii) Constraint (4)
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
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
(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