FIT5216: Modelling Discrete Optimization Problems

Assignment 2: Testing Vaccines

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 (20th April 2020, 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 3 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

In the race to find an effective vaccine for COVID-19 the World Health Organization is a trialing

different potential vaccines developed by different medical research groups around the world1. The

vaccines are given as an enumerated type:

enum VACCINE;

To determine the effectiveness of each vaccine they need to trial it across many groups of test

participants with many different features.

The participants are defined by features

enum AGE = { BABY, CHILD, YOUTH, ADULT, SENIOR, AGED, ANCIENT };

enum GENDER = { FEMALE, MALE, OTHER };

enum HEALTH = { GOOD, POOR, COMPROMISED };

enum EXPOSURE = { LOW, AVERAGE, HIGH, EXTREME };

The participants are divided into groups with similar features. There are m groups, and all of

the participants in a group have the same features. The groups are not all the same size. The data

is available as

1This is a fictional scenario, and completely made up! It does not reflect any actual testing going on at the

moment. But this type of problem, called an experiment design, is quite common in practice.

1

int: m; % number of groups

set of int: GROUP = 1..m;

array[GROUP] of AGE: age; % age of the group

array[GROUP] of GENDER: gender; % gender of the group

array[GROUP] of HEALTH: health; % underlying health of the group

array[GROUP] of EXPOSURE: exposure; % exposure for the group

array[GROUP] of int: size; % number of people in the group

The aim is to assign treatments to groups in order to gain the most possible knowledge of the

effectiveness of different potential vaccines.

The decisions are then for each group, the set of vaccines to be applied to members of the group.

Each participant will get only one vaccine, but we want to trial different vaccines for each group to

get the most information in this experiment.

array[GROUP] of var set of VACCINE: x;

The constraints on the assignment are as follows:

1. In order for the tests to be reliable we need to replicate the test on at least minsize people in

each group. So we can’t assign a number of vaccines to a group bigger than the size dictates.

For example, if minsize=4, and a group has 14 participants, we can assign at most 3 vaccines

to the group (since 3*minsize <=14, but 4*minsize > 14).

2. To find the effect of vaccines on different ages the decision must balance vaccine applications

across the age types. Since the number of groups of each age type are very different we give

minimum age group min and maximum age group max for the each age type. Each vaccine

must be applied to a number of groups for each age type within these bounds.

3. If a group is tested with k vaccines then the number of people tested for each vaccine is

size div k, that is each vaccine is applied evenly. We want to balance the number of people

trialled for each vaccine. For any pair of vaccines v1 and v2, the difference between the total

number of people trialled for v1 and the total number of people trialled for v2 cannot be more

than max people diff;

4. To avoid any possibility that the trial is gender biased, for each gender type we must have

exactly the same number of groups of that type for each vaccine.

5. To improve the statistical predictive ability of the trial we need to spread out the use of

vaccines across different groups. For any two groups the maximum number of vaccines they

can share is at most max share vaccines.

The data for these constraints is given by

int: minsize;

array[AGE] of int: age_group_min;

array[AGE] of int: age_group_max;

int: max_people_diff;

int: max_share_vaccines;

2

The objective of the trial is to discover the most information possible. The effectiveness of the

vaccine will be tested most efficiently in participants with lower health and higher exposure, since

here the statistical likelihood of the participant being critically affected by COVID-19 is higher.

The information gain for each vaccine in the trial is calculated by adding the information value

for each group by its health and exposure. The data is given as

array[HEALTH] of int: health_information;

array[EXPOSURE] of int: exposure_information;

For a group g treated with vaccine v we gain information about that vaccine equal to the

health information[g]× exposure information[g]

units. The objective is to maximise the minimum information gain over all vaccines.

For example a sample data set is

VACCINE = { ACOV, RETROV, ANTIFLU };

m = 10;

age = [BABY, CHILD, YOUTH, ADULT, AGED, YOUTH, BABY, ADULT, ADULT, ANCIENT];

gender = [MALE, FEMALE, OTHER, MALE, FEMALE, MALE, FEMALE, MALE, MALE, FEMALE];

health = [GOOD, POOR, GOOD, COMPROMISED, GOOD, GOOD, POOR, POOR, POOR, COMPROMISED];

exposure = [LOW, HIGH, LOW, AVERAGE, EXTREME, LOW, HIGH, AVERAGE, AVERAGE, AVERAGE];

size = [10, 35, 10, 100, 46, 60, 18, 145, 170, 12];

minsize = 9;

age_group_min = [0,0,0,1,0,0,0];

age_group_max = [1,1,1,2,1,1,1];

max_people_diff = 20;

max_share_vaccines = 2;

health_information = [1,2,4];

exposure_information = [1,2,5,7];

A solution (not necessarily the best) is given by

x = [{ANTIFLU}, {RETROV, ANTIFLU}, {}, {ANTIFLU}, {RETROV, ANTIFLU}, {ACOV, RETROV},

{ACOV}, {ACOV, RETROV}, {ACOV, RETROV, ANTIFLU}, {ACOV}];

Let’s examine the constraints.

The maximum number of vaccines applicable to the first, third and last group is 1 because of

their size, and that holds. The maximum number for the 7th group is 2, that also holds. All the

rest can have 3.

Each number of groups for each age type is given by

AGE BABY CHILD YOUTH ADULT SENIOR AGED ANCIENT

ACOV 1 0 1 1 0 0 1

RETROV 0 1 0 2 0 1 0

ANTIFLU 1 1 0 2 0 1 0

3

Clearly the min and max constraints hold.

The total number of participants trialled with each vaccine is 188, 198 and 206 with the maxi-

mum difference only 18.

The number of groups trialled for each gender and vaccine is

GENDER FEMALE MALE OTHER

ACOV 2 3 0

RETROV 2 3 0

ANTIFLU 2 3 0

so each vaccine is trialled on an equal number of groups for each gender.

The maximum number of vaccines shared by any group is 2, since there is only one group

trialling all three vaccines.

The minimum information is for vaccine RETROV with 26 information units. The information

gain for RETROV for each group is

GROUP 2 5 6 8 9

health POOR GOOD GOOD POOR POOR

exposure HIGH EXTREME LOW AVERAGE AVERAGE

info 10 7 1 4 4

Write a MiniZinc model vaccine.mzn which models the above problem.

3 Full Objective

To achieve full marks you need to tackle this extension. Grading of the solutions will be done based

on this “true form” of the objective.

The aim is really to test the vaccine on as many different categories of health and exposure as

possible. The true information gain is more complicated than discussed above.

For a group g treated with vaccine v we gain information about that vaccine equal to the

health information[g] × exposure information[g] units. But we only gain this from the first group

with this combination of HEALTH and EXPOSURE, for each other group treated by this vaccine

with the same combination we simply get information of 1 unit. The objective is to maximise the

minimum information gain over all vaccines.

For the solution above then minimum information is for vaccine RETROV with 23 information

units. The information gain for RETROV for each group is

GROUP 2 5 6 8 9

health POOR GOOD GOOD POOR POOR

exposure HIGH EXTREME LOW AVERAGE AVERAGE

info 10 7 1 4∗ 4∗

where the last two groups have the same combination so we replace one of the 4s by 1.

4 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.

5 Marking

The marks are automatically calculated.

The submission has 8 marks for locally tested data and 14 for model testing, for a total of 22

marks.