共计 4454 个字符，预计需要花费 12 分钟才能阅读完成。
FIT5216: Modelling Discrete Optimization Problems
Assignment 1: Air Defence
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:
1
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 9×5 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.
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
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 x 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.
2
Part B – Bounded Number of Equipment
Modify your model airdefence.mzn to treat limit as a bound on the maximal possible number
of equipment. For example an optimal profit for the example data is illustrated by the solution,
where PATRIOT positions are shown as dark purple.
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
The number of equipment is 3 with a total cost of 14. The protected value is improved to 34.
To model this extension, unused equipment slots must be defined as having x and y coordinate
- The type t of the unused equipment can be anything. All the unused slots must occur at the
end of the x, y and t lists. So a correct output for this solution is:
x = [2, 1, 4, 0];
y = [2, 5, 3, 0];
t = [S300, S300, PATRIOT, NASAMS];
total_protection = 34; - Instructions
Edit the provided mzn model files to solve the problems described above. You are provided with
some sample data files to try your model on. Your implementations can be tested locally by using
the Run+check icon in the MiniZinc IDE. Note that the checker for this assignment will only
test whether your model produces output in the required format, it does not check whether your
solutions are correct. The checker on the server will give you feedback on the correctness of your
submitted solutions and models. - Marking
The marks are automatically calculated.
For most instances you can get a maximum of 0.75 for part A and 1 (full marks) for part B.
For some instances you can get full marks with part A.
For some instances you will always get 0 with part A.
The submission has 10 marks for locally tested data and 10 for model testing, for a total of 20
marks.
