FIT5220 Solving Discrete Optimization Assignment 3: Feast Trap
Semester T3, 2021
Due: Monday August 16, 11:59pm
Overview
In this assignment, you will develop MiniZinc encodings for a given problem, suitable for integer program-
ming and Boolean satisfiability solvers. The topics are MIP (meaning Weeks 4 and 5) and SAT (meaning
Weeks 6 and 7).
• Submit your work to the MiniZinc auto grading system (using the submit button in the MiniZinc
IDE).
• Submit your model (upload the trap_mip, trap_predicates and trap_sat .mzn files), and a PDF
document with your answers to the questions that cannot be solved directly with a MiniZinc model,
using the Moodle assignment.
• You have to submit by the due date (Monday August 16, 11:59pm), using both 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!
• Submit a PDF document with your answers to the questions that cannot be solved directly with a
MiniZinc model.
Task: Feast Trap
In FIT5216, you developed a model for the Feast trap problem. Here we solve a slightly modified version:
Wang Yun begins a plot to help defeat Dong Zhou. He sets out to have both Dong Zhou and his
best fighter Lu¨ Bu fall for his foster daughter Diao Chan, who is a remarkable beauty. When
Dong Zhou is invited to Wang Yun’s house Diao Chan prepares a magnificient banquet in order
to seduce him. This feast trap is the first part of the “beauty trap”.
Diao Chan must plan the most magnificent feast possible. The sequence of dishes must be
exquisite and balanced so that the whole sequence is a magnificient meal.
Diao Chan knows a number of dishes she can make. She can only serve each dish once, obviously.
Each dish tastes spicy, sour, salty, sweet, umami or bland. She should not serve two dishes of the
same taste in a row. The first dish should be salty, and the last dish should be sweet. After a
spicy dish the next dish must be bland or sweet. After a sour dish the next dish must be bland
or umami. No umami dishes directly after a sweet dish.
Each dish is served hot, cold or warm. Between serving a hot dish and a later cold dish there
must be a warm dish.
Each dish is either heavy on the stomach or light. Diao Chan’s banquet cannot have more than
2 heavy dishes in a row.
Her aim is to maximize the magnificence of the meal, which is given by number of changes in
taste, temperature and weight.
This objective is different from the original Feast Trap problem.
1
Data Format Specification
Data for the problem is defined as follows: The input form for the Feast Trap is a file named data/feasttrap *.dzn,
where p is the problem number with len is the number of courses, DISH is a set of dishes, taste is an array
mapping dishes to taste, temp is an array mapping dishes to temperature, heavy is an array of Booleans
showing which dishes are heavy, value is an array mapping dishes to their value in magnificence. The
decisions are dish which is an array of length len showing which dish is offered in each course.
The data declarations and decisions are hence:
enum DISH;
enum TASTE = {spicy, sour, salty, sweet, umami, bland};
enum TEMP = {hot, cold, warm};
array[DISH] of TASTE: taste;
array[DISH] of TEMP: temp;
array[DISH] of bool: heavy;
array[DISH] of int: value;
int: len; % length of banquet
set of int: COURSE = 1..len;
array[COURSE] of var DISH: dish;
An example data file is
len = 6;
DISH = { MAPOTOFU, KUNGPAOCHICKEN, COCONUTJELLY, LAIWONGBAO, CHARSIUBAO,
SESAMEPRAWN, HOTSOURSOUP, CHILIDUMPLINGS, GLASSNOODLES, FRIEDRICE };
taste = [umami, spicy, sweet, sweet, salty, salty, sour, spicy, bland, bland];
temp = [ hot, hot, warm, cold, warm, warm, hot, hot, cold, warm];
heavy = [ true, true, false, false, false, true, true, true, false, false];
value = [ 8, 4, 5, 3, 5, 7, 4, 3, 2, 1 ];
which considers a 6 course banquet chosen from 10 possible dishes. Your model should contain a decision
variable dish which decides what is served for each course, and an objective variable obj defining the
objective. For example it might output
dish = [SESAMEPRAWN, GLASSNOODLES, MAPOTOFU, CHARSIUBAO, KUNGPAOCHICKEN, COCONUTJELLY];
obj = 15;
The objective of 15 arises from 5 changes in taste [salty, bland, umami, salty, spicy, sweet], 5
changes of temperature [warm, cold, hot, warm, hot, warm], and 5 of weight [true, false, true,
false, true, false].
Part A - Encoding for MIP [12 marks]
Your first task will be to encode the constraints in the simplified feast trap problem in a form suitable for
MIP.
1. Complete following predicates in trap_predicates.mzn:
• predicate taste_constraint(array [LEN, TASTE] of var 0..1: course_taste);
which enforces all constraints on course taste, assuming that course_taste[i, t] = 1 if and
only if the dish of course i has taste t. [2 marks]
• predicate temp_constraint(array [LEN, TEMP] of var 0..1: course_temp);
which enforces all constraints on temperature, assuming that course_temp[i, t] = 1 if and
only if the dish of course i has temperature t. [2 marks]
• predicate temp_heavy(array [LEN] of var 0..1: course_is_heavy);
which enforces all constraints on weight, assuming course_is_heavy[i] = 1 if and only if the
dish of course i is heavy. [2 marks]
You should test each of these predicates using the check-predicates solver configuration (which is
gecode in all solutions mode, using the -G stdlib flag). You should not remove the include "forbid.mzn";
lines, as this ensures only MIP constraints are permitted.
2. The objective requires computing the number of changes in taste, temperature and weight Describe
(in your report) how you would convert this into MIP constraints, and why you chose the particular
encoding. [2 marks]
3. Complete the MiniZinc model trap-mip.mzn for the feast trap problem, including all constraints
and the objective. [4 marks]
Important: For all parts of this task, your model should only generate constraints which are suitable for
a MIP solvers. The MIP solver only supports linear equalities and inequalities. You can still use high-level
constructs that will be flattened away (so top-level foralls, array comprehensions over par sets, and array
lookups with par indices are all fine). For local testing, make sure you are running the check-model
solver configuration, runs is Coin-BC with the additional compiler option -G std.
Part B - Encoding for SAT [8 marks]
Your second task is to encode the the problem in a form suitable for SAT solvers. For this task, your
model should only use Boolean variables, and produce clauses (clause constraints).
For this task we will solve a satisfiability version of the problem: the task is design a meal which
which satisfies all constraints on taste, temperature and weight while reaching at least a specified level of
magnificence. The data will have an additional parameter:
int: min_magnificence;
And as we cannot use integer variables, decision variables will instead be:
array [LEN, DISH] of var bool: course_dish;
1. Complete the model trap_sat.mzn for the Feast Trap problem, using only constraints suitable for
SAT solvers. In your report, explain how you encoded the magnificence constraint.
[4 marks (model) + 2 marks (report)]
2. Select one large instance. Solve it twice with chuffed using your SAT model: selecting the magnif-
icence limit first as the best solution found by MIP, and then as one more than that value. Compare
the performance of this with your MIP solution. Using the reported solver statistics, explain what
you think is happening inside the solvers that causes the difference in performance. [2 marks]
Hint: Your model should only generate Boolean variables and clause constraints. You should test your
model locally using the trap_sat_wrap.mzn (which includes trap_sat.mzn) and the check-sat solver
configuration (which is chuffed using the flag -G std).
Submit your modified models using the MiniZinc IDE and Moodle. Submit your answers to the other
questions as part of your PDF report document.
Marking
This assignment is worth 20% of your unit marks. The autograder will used to evaluate correctness and
quality of your model (10 marks for part A, and 4 marks for part B.1). The report will be assessed based
on demonstrated understanding of the behaviour of the underlying solvers.

欢迎咨询51作业君