1    Overview

For this assignment, your task is to write a MiniZinc model for a given problem specification.

● Submit your work to the MiniZinc auto grading system  (using the submit button in the MiniZinc IDE).

● Submit your model (copy and paste the contents of the .mzn file) using the Moodle assignment.

You have to submit by the due date (26th March 2023, 11:59pm), using MiniZinc and using the Moodle assignment, to receive full marks.  You can submit as often as you want before the due date. Late submissions without special consideration receive a penalty of 10% of the available marks per day. Submissions are not accepted more than 7 days after the original deadline.

This is an individual assignment. Your submission has to be entirely your own work. We will use similarity detection software to detect any attempt at collusion, and the penalties are quite harsh. If in doubt, contact your teaching team with any questions!

2    Problem Statement

Your task is to plan the air defence of a small region of a country under attack.  The area for defending is a rectangle which is subdivided into W × H cells. You need to decide a set of locations to place air defence equipment. Each cell has a value for defending it.

The goal is to defend the most value within the given constraints. For task (a) you are given a fixed number of equipment. For task (b) you are planning for a maximum number of equipment.

Each air defence equipment location must be at least 3 cells distant from any other equipment location: e.g. have a Manhattan distance of at least 3, otherwise the sensing methods can interfere. You cannot place equipment on cells with value 0 (which represents enemy control).  You cannot use more of a type of equipment than is available.

You have a given budget, which is the maximum cost you can spend on equipment. Input data is given in MiniZinc data format:

W  =  (  width  ) ;

H  =  (  height  ) ;

value  =  (  2D W × H  array  of  value  of position  ) ;

EQUIPMENT  =  (  An  set  of possible  equipment  types  ) ;

cost  =  (  cost  of  each  type  of  equipment  ) ;

avail  =  (  number  available  of  each  type  of  equipment  ) ;

radius  =  (  radius  at  which  each  equipment  protects  ) ;

limit  =  (  limit  on  total  number  of  equipment)  ) ;

budget  =  (  defense  budget  ) ;

Here is a sample data set:

W  =  9;

H  =  5;

value  =  [|  0,  0,  1,  0,  0,  0,  0,  0,  0

|  1,  4,  1,  1,  1,  1,  0,  0,  0

|  1,  1,  4,  1,  1,  2,  1,  0,  0

|  1,  2,  2,  2,  1,  0,  0,  0,  0

|  1,  1,  1,  1,  1,  1,  0,  0,  0  |];

EQUIPMENT  =  {  S300,  NASAMS,  PATRIOT  };

cost  =  [  3,  5,  8  ];

avail  =  [  3,  3,  1  ];

radius  =  [1,  2,  3];

budget  =  15;

limit  =  4;

On this 9x5 grid, there are 3 types of equipment, with different costs, availability, and defence radius. We need to place (at most) 4 equipment for maximum coverage with a budget of 15.

Part A - Fixed Number of Equipment

Create a model airdefence .mzn that takes data in the format specified above and decides on exactly limit different air defence locations.

Here is a sample solution. The S300 positions are represented in light blue, NASAMS positions in light purple the defended areas are in light gray.

Note that there are 4 equipment, as required.  None of the equipment is closer than 3 squares to another equipment, and no equipment is on a zero reward (red) cell. The total protected value is 33 the sum of the coloured

Your model must define the positions of the equipment cells as 北 and y coordinates and their type, together with the total protected value. One correct output for the solution above is

x  =  [5,  2,  1,  3];

y  =  [3,  2,  4,  5];

t  =  [NASAMS,  S300,  S300,  S300];

total_protection  =  33;

Note that you will not be able to obtain full marks by just answering part A. Some problems will have no solution, whereas using part B they have a solution.