FIT5216: Modelling Discrete Optimization Problems
Assignment 3: Sound Planning
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). You must submit via the IDE to be graded and receive marks.
• Submit your model (copy and paste the contents of the .mzn file) using the Moodle assignment.
You have to submit by the due date (Sunday 9th May 2021, 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% 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
Organizing the sound system at a major event is a complex task, and can be very expensive.
The aim of this assignment is to design a sound system for a concert that will deliver the sound
requirements and be robust for the cheapest price.
The most basic component in the sound design are the sound ranges
enum RANGE = { RUMBLE, BASS, TREBLE, TWEET };
For each range there is a desired decibel output from the system
array[RANGE] of int: total_db;
The most important component in the sound design are the speakers, each of which can connect
trhough some range of connection inputs:
enum SPEAKER;
SPEAKER: dummys = max(SPEAKER); % the last speaker is a dummy
array[SPEAKER] of int: db; % volume output
enum CONNEX = { COAX, DIGITAL, STEREO, MONO };
array[SPEAKER] of set of CONNEX: speaker_input; % possible inputs
array[SPEAKER] of RANGE: speaker_range; % output range
array[SPEAKER] of int: weight; % speaker weight
array[SPEAKER] of int: speaker_available; % number available of each type
array[SPEAKER] of int: speaker_price; % price to hire
int: max_speaker; % maximum number of speakers
set of int: SPEAKNUM = 1..max_speaker; % numbered speakers
constraint assert(speaker_price[dummys] = 0,"dummy speaker costs 0\n");
1
You can assume that the speaker price for the dummy speaker is 0.
Speakers are place in housings, that stack multiple speakers. Each housing is in one position
around the audience.
enum HOUSING;
HOUSING: dummyh = max(HOUSING); % last housing is a dummy
array[HOUSING] of int: weight_limit; % total weight in housing
array[HOUSING] of int: speaker_limit; % total speakers in housing
array[HOUSING] of int: housing_available; % number of each housing available
array[HOUSING] of int: housing_price; % price to hire
enum POSITION = { LEFT, CENTRE, RIGHT, BEHIND };
int: max_housing; % maximum number of housings
set of int: HOUSENUM = 1..max_housing; % numbered housings
constraint assert(housing_price[dummyh] = 0,"dummy housing costs 0\n");
You can assume that the housing price of the dummy house is 0.
The sound board drives the speakers
enum SOUNDBOARD;
array[SOUNDBOARD] of set of CONNEX: board_output; % output connections
array[SOUNDBOARD] of int: board_lines; % number of speakers supported
array[SOUNDBOARD] of int: board_price; % price to hire
The key decisions are:
var SOUNDBOARD: master; % which soundboard to control the entire system
array[HOUSENUM] of var HOUSING: housing; % housing that are hired
array[HOUSENUM] of var POSITION: position; % position of housing
array[HOUSENUM] of var set of SPEAKNUM: housed; % numbers of speakers housed
array[SPEAKNUM] of var SPEAKER: speaker; % speakers that are hired
The constraints in designing the system are as follows:
• We cant hire more of any item: speakers or housings, than is available.
• We cant put more than speaker limit different speakers in a housing.
• We cant put more than weight limit of total speaker weight in a housing.
• We cant run more speakers than board lines.
• The soundboard cannot run a speaker unless they share a connection type (CONNEX);
• The total decibel db of speakers supporting some range r should be at least total db
• The total decibel db of speakers housed to the LEFT and RIGHT should differ by no more
than 10% of the total db in each range.
• The total decibel db of speakers housed to the LEFT and RIGHT should be at least 20% of
the total db in both TREBLE and BASS.
2
• The total decibel in position BEHIND can be at most 10% of total db in each range except
in RUMBLE where it should be at least 20%.
• The total decibel in position CENTRE should be at least 20% and no more than 50% of total db
for the TREBLE range.
• The number of housings on LEFT and RIGHT should be the same.
The aim is to minimize the total price of the sound system, paying for each component hired.
3 Stage A
In this stage you need to develop a model to encompass the problem as described above. For
example given a data set defined by
total_db = [ 0, 10, 9, 2];
SPEAKER = { W1, B1, B2, T1, T2, TW1, TW2, DUMMYS };
db = [ 6, 5, 4, 4, 3, 1, 2, 0 ];
speaker_input = [ {COAX, DIGITAL}, {STEREO}, {STEREO}, {MONO},
{STEREO}, {STEREO}, {MONO}, {} ];
speaker_range = [ RUMBLE, BASS, BASS, TREBLE, TREBLE, TWEET, TWEET, TWEET ];
weight = [ 4, 3, 2, 3, 2, 0, 0, 0];
speaker_available = [1, 2, 2, 4, 4, 2, 2, 0];
speaker_price = [40, 30, 20, 20, 15, 5, 2, 0];
HOUSING = { TALL, WIDE, SINGLE, DUMMYH };
weight_limit = [ 10, 12, 4, 0 ];
speaker_limit = [ 4, 4, 1, 0 ];
housing_available = [ 4, 4, 6, 0 ];
housing_price = [ 10, 10, 4, 0 ];
SOUNDBOARD = { WEXEL_ANCHOR, MASTER_BEE };
board_output = [{COAX,MONO,STEREO}, {STEREO}];
board_lines = [ 9, 7];
board_price = [ 40, 20];
max_housing = 4;
max_speaker = 8;
which defines 8 different speaker types (the last is a dummy) and 4 different housing types (the
last a dummy), and two possible sound boards. One possible solution is
master = WEXEL_ANCHOR;
housing = [WIDE, WIDE, WIDE, TALL];
position = [CENTRE, LEFT, RIGHT, BEHIND];
housed = [6..6, {2,3,8}, {1,5,7}, {}];
speaker = [B1, TW1, T2, DUMMYS, T2, T2, TW1, B1];
3
which has a total cost of 195. The WIDE housing on the LEFT contains a TW1, T2 and B1
speaker, so does the WIDE housing on the right. This is clearly not optimal, for example the
TALL housing situated BEHIND contains no speakers.
Document your model with comments that briefly explain your modelling decisions. Use the
chuffed solver for testing your model, since chuffed will be used for grading the assignment.
4 Stage B
There are a number of symmetric ways of essentially describing the same solution to the sound
design problem. If you allow multiple ways to describe the same solution then you can make the
solving, and in particular the proof of optimality much harder.
For this stage you need to write a report of two pages, which describes what kinds of solutions
for the master, housing, position, and speaker are defining equivalent sound designs.
In the report you should include a detailed description (i.e. the actual MiniZinc code) and an
explanation of the constraints you have added to your model to prevent the model from allowing
two effectively equivalent solutions.
5 Stage C
The constraint for sound balance have been simplified up until now. The real constraints for sound
balance are as follows:
• The total decibel db of speakers housed to the LEFT and RIGHT should differ by no more
than 10% of the total output in each range.
• The total decibel db of speakers housed to the LEFT and RIGHT should be at least 20% of
the total output in both TREBLE and BASS.
• The total decibel in position BEHIND can be at most 10% of total output in each range except
in RUMBLE where it should be at least 20%.
• The total decibel in position CENTRE should be at least 20% and no more than 50% of total
output for the TREBLE range.
The total output in each range is the sum of all the speakers db in the sound design solution that
support that range.
Modify your model to make use of the real constraint on sound balance. Write in your report a
one page explanation of how you handled these constraints, and what makes them harder than the
simplified form of the constraints. Explain how you chose to represent the constraints in a way that
should be as easy for solvers to handle as possible. Explain which original simplified constraints
you might want to keep in the model and why!
Compare the performance of the model with and without the real sound balance constraints.
In your report show a table across the data files s1.dzn, s2.dzn, s3.dzn, s4.dzn and s5.dzn
comparing the runtime and cost of solution for the stage A and stage C version of your model.
Explain the behaviour you see in the table.
4
6 Stage D
Sometimes it can be easy to see that some designs will not be possible given the input data. For
example if we modify the data file above to have total db = [6,10,9,2] then since the the only
RUMBLE speaker has only COAX and DIGITAL inputs we cannot use the MASTER BEE sound
board in any solution.
Add redundant constraints to your model that help reduce the number of possible solutions
explored. Create a new data file for the problem named yourusername.dzn that allows as many as
possible of the redundant constraints you define to be applied, and submit it as part of the Moodle
submission. In one page in your report explain the redundant constraints you added, and how
they restrict the possible solutions explored, and give a table showing the effect of each redundant
constraint on your newly constructed data file, in terms of time to solve and failure (a search
statistic available in chuffed). Note that often you wont expect to see too much improvement in
adding them.
7 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 icon in the MiniZinc IDE or by using,
minizinc ./modelname.mzn ./datafile.dzn
at the command line.
The report has to be submitted in PDF format. It does not have to follow any particular
structure (e.g. you do not need an abstract, table of contents etc.). The explanations should be
concise. The overall limit for the report is 4 pages, including all graphs, tables etc.
8 Marking
The auto-grading server is using the chuffed solver to grade this assignment. Grades are calculated
based first on the correctness of the found solutions, and then on the quality of solution that is
achieved. Your model needs to be able to find at least one solution for each instance within the 1
minute time-out in order to get any marks.
You can get a maximum of 30 marks for this assignment, which will be worth 15% of your
overall unit marks.
The marks for the correctness of your model are automatically calculated. You will receive up
to 5 marks for locally tested data and up to 10 marks for your model as tested on the auto-grading
server. You will only get full marks if you implement all stages.
The code comments and your report will be marked by your tutors, and they are worth the
remaining 15 marks, with the following allocation:
Stage A (code comments): 3 marks; Stage B (symmetry): 6 marks; Stage C (balance): 3 marks;
Stage D (redundant): 3 marks;
5

欢迎咨询51作业君