P is constrained to be non-negative, with row-sums equal to 1. We interpret pjk as the proba- bility that job j is assigned to agent k.

For testing our GAP code we will use examples from the OR-Library, maintained by J.E.Beasley http://people.brunel.ac.uk/~mastjjb/jeb/info.html

Part 1

In Parts 1 and 2 we will be completing the code gap CE outine.r provided on the module webpage. For Part 1 complete the objective function:

                 loss(x, costs, resources, capacities, lambda)

where
ˆ x is a vector of length n giving an assignment;
ˆ costs is an n × m matrix giving the costs;
ˆ resources is an n × m matrix giving the resource requirements;
ˆ capacities is a vector of length m giving the capacity constraints; ˆ lambda is the penalty coefficient.

You can check your objective function is working with the following code. It assumes that the files read gap.r and gap1.txt are in the working directory (you can find them on the module webpage).

> source("read_gap.r")
> set.seed(2024)
> for (case in 1:length(gaps)) {

• +    gap <- gaps[[case]]
  

• +    n <- dim(gap$costs)[1]
  

• +    m <- dim(gap$costs)[2]
  

• +    x <- sample(1:m, n, replace = TRUE)
  

• +  print(loss(x, gap$costs, gap$resources, gap$capacities, 1)) +}
  [1] 397
  [1] 372
  [1] 356
  [1] 400
  [1] 371

  Part 2

  Complete the function gen assignment(P) for generating an assignment from f(·;P), where

  ˆ P is a non-negative n × m matrix whose rows sum to 1.

  Complete the function sample P(samples, m) for calculating the most likely P for a given set of sample assignments, where

  ˆ samples is a matrix with n rows such that each column is a sample assignment;

  ˆ m the entries of samples are in {1,…,m}
  You must look at the first task for Part 3 before starting!

2

Part 3

For Part 3 you will need to submit two files: a programme file titled YOUR NAME assign3.r and a report as a pdf file titled YOUR NAME assign3.pdf. Submission by email to joneso18@cardiff.ac.uk.

The report should be typed in a 12 point font and should be no more than four pages long (ex- cluding figures). You must express yourself in your own words and acknowledge your sources: see the university rules on academic misconduct https://intranet.cardiff.ac.uk/students/study/exams- and-assessment/cheating-and-academic-misconduct

Your code must be submitted as a single file, and must be properly documented, including clear instructions on how to run the code. Data files may be included separately. See the module website for restrictions on the external libraries you can use, and note that jupyter notebooks are not accepted.

Very important: your assessment is based on the report! You must submit your code, and I will look at it to check how well you have documented your additions, but I expect you to explain what you have done and present your results in the report. I will usually only run your code if it is not clear what is going on from the report, in which case you will probably be losing marks. Of course, should I choose to run your code, it must be capable of reproducing the results presented in the report.

Presentation, clarity of expression, and documentation of code will be taken into account when marking your report.

(a) (8 marks) For i = 1,…,M let xi = (xi(1),…,xi(n))T be an element of Ω. Prove that

the matrix P that solves

is given by

M maxXlogf(xi; P)

i=1

pjk = M1 #{i : xi(j)=k}
(b) (4 marks) For the complete code, how does the quality of your solution depend on N, rho,

alpha, and lambda?
Your answer should be backed up by numerical results, which should be based on all five

examples provided in the file gap1.txt.

(c) (4 marks) Modify the code so that the smoothing parameter decays like α/t where t is the iteration number, and replace the fixed number of iterations with the stopping condition that γ has not decreased for the last four iterations.

How does this effect the quality of your results?

References

Beasley, J.E., 1990. OR-Library: distributing test problems by electronic mail. Journal of the Operational Research Society, 41(11), pp.1069–1072.

Cattrysse, D.G. and Van Wassenhove, L.N., 1992. A survey of algorithms for the generalized assignment problem. European Journal of Operational Research, 60(3), pp.260–272.

Pentico, D.W., 2007. Assignment problems: a golden anniversary survey. European Journal of Operational Research, 176(2), pp.774–793.