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 informa
tion 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 4 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. 5
