1. Introduction

In this coursework, you are asked to write a C/C++/Python program to solve a classic number  puzzle using a variable neighbourhood search method. In addition to submitting source code,  a written report (no more than 2000 words and 6 pages) is required to describe your                 algorithm (see Section 4 for detailed requirements). Both your program and report must be      completed independently by yourself. The submitted documents must successfully pass a

plagiarism checker before they can be marked. Once a plagiarism case is established, the academic misconduct policies shall be applied strictly. 

This coursework carries 45% of the module marks.

2. Magic Square Problem (MSP)

Magic Square Problem (MSP) is a recreational game that has fascinated mathematicians for thousands of years, with the earliest known example dating back to 2,800 B.C.E., in China. The player is given distinct n2 integers and is asked to arrange them over a n*n matrix such that the n numbers in all rows, all columns and both diagonals sum to the same constant M (often called magic constant). See Figure 1 below for a magic square for n=3.

15

Figure 1: The magic square for n=3 and M=15

.   Statistical results (avg, best, worst of 10 runs) of the algorithm for all the problem instances, Note that although your report should include results for 10 runs but    your final submission should only have one single run for each instance (i.e. set   global variable NUM_OF_RUNS=1 before you submit the code).

.   A short discussion/reflection on results and performance of the algorithm. 

(4) Name your program file after your student id. For example, if your student number is 2019560, name your program as 2019560.c (or 2019560.cpp, or 2019560.py).

(5) Your program should compile and run without errors on either CSLinux Server or a computer in the IAMET406 (the new computer lab). Therefore, please fully tested

before submission. You may use one of the following commands (assuming your student id is 2019560 and your program is named after your id):

gcc -std=c99 -lm 2019560.c -o 2019560

or

g++ -std=c++11 -lm  2019560.cpp -o 2019560

For remote study students with poor connection to CSLinux, please contact GTAs ([email protected] or [email protected]) for support.     They’ll be able to help test your program on CSLinux.

(6) After compilation, your program should be executable using the following command:

./2019560 -s data_fle -o solution_file -t max_time     where 2019560 is the executable file of your program, data_file is one of         problem instance files specified in Section 3. max_time is the maximum time          permitted for a single run of your VNS algorithm. In this coursework, maximum of 100 seconds is permitted. soluton_file is the file for output the best solutions

by your VNS algorithm. The format should be as follows:

# of problems                                                      

… …

x_ (n-1)0 x_ (n-1)1… … x_ (n-1)(n-1)    #row (n-1)

x_00 x_01  x_0(n-1)                 #row 0

x_10 x_11  x_1(n-1)                 #row 1

… …

x_ (n-1)0 x_ (n-1)1… … x_ (n-1)(n-1)    #row (n-1)

… …

An example solution file for problem data file “example_sln.txt” is available on 

moodle for reference.

For submissions using Python, the compilation and running are combined in one command as follows:

python 2019560.py -s data_fle -o solution_file -t max_time

(7) The solution file output in (6) by your algorithm (solution_file) is expected to pass a solution checking test successfully using the following command on CSLinux:

./msp_checker -s problem_file -c solution_file

where problem_file is the problem data files mentioned in Section 3. If your solution file format is correct, you should get a command line message similar to: “You total score out of xxx instances is: xxx." If the solutions are infeasible for some      instances, you would get error messages.

The solution checker can be downloaded from moodle page.  Please make sure that correct permissions are set by using chmod when you run the checker program.

(8) Your algorithm should run only ONCE for each problem instance and each run should take no more than 100 seconds. You should stop the algorithm as soon as the               objective reaches zero, meaning a perfect solution is found.

(9) Please carefully check the memory management in your program and test your           algorithm with a full run on CSLinux (i.e. running multiple instances in one go). In    the past, some submitted programs can run for 1-2 instances but then crashed because of out-of-memory error. This, if happens, will greatly affect your score.

(10) In order to practice and evaluate your skills and knowledge for intelligent                optimisation algorithm design (i.e. VNS), your algorithm must start from a random 

initial solution or a solution that initialises the magic square matrix row by row

sequentially by strictly following the given order of the numbers from the problem 

data file. You should not use any greedy heuristics, including those that produce

optimal solutions.

(11) You must strictly follow policies and regulations related to Plagiarism. You are  prohibited from using recent AI tools like ChatGPT/GPT-4 or other similar large language models (LLMs). Once a case is established, it will be treated as a          plagiarism case and relevant policies and penalties shall be applied.

5. Marking criteria

.   The quality of the experimental results (total 25 marks). Your algorithm shall be       tested for a file containing 5 instances chosen from the provided set of instances. The

performance of your algorithm is evaluated by computing the absolute deviation from 

the magic constant M.

.   The quality of codes (total 5 marks). Mainly checking the structure of your     program/functions, clarity and succinctness of comments and variable naming.

.   Report (total 15 marks). Description of your algorithm,

6. Submission deadline

May 4th 2023, 4pm China Time.

7. How to submit

Submit via Moodle.

8. Practical Hints

.   You are suggested to work out a basic version of the algorithm first, focus on improving the quality of the solutions first and relax the restriction on the      computational time at the beginning.

.   Your choice of neighbourhoods does not have to strictly follow the inclusivity rule (i.e. neighbourhood 1 is completely covered by neighbourhood 2, and so on.). A     common way to design neighbourhood is the k-opt, where k denotes the amount of changes from the incumbent solution. For example, k=2 means that exactly 2          numbers in the magic square matrix change their positions, while k=3 means          exactly 3 numbers change their positions. Additionally, you may also think about more targeted neighbourhood moves that mimic human players problem solving strategies.