This archive contains a large number of instances for the Hospital-Residents with Ties (HRT) and Hospital-Residents with Ties and Couples (HRTC) problems, as well as our experimental results on solving these instances. For a background on these problems, see Algorithmics of Matching Under Preferences by Prof. David Manlove (World Scientific, 2013). The archive contains two zip-files: HRCT_Instances.zip and Solutions.zip. We describe these now, beginning with HRCT_Instances.zip # HRCT_Instances.zip ## File naming The files are named according to the following convention: ____ with possible modifiers appended. The variables are as follows: num_doctors: the number of doctors (single or in a couple) in the instance num_spaces: the total sum of capacities across all hospitals num_hospitals: the number of distinct hospitals preference_length: the length of preferences of single doctors The second appearance of preference_length allows a different preference length to be allocated to doctors who are in couples, we keep this the same as for single doctors. The following modifiers may also be present: TRANSFORMED - couples in this instance do not allow partial assignment SEPARATE - couples in this instance do allow partial assignment P0/P40/P60/P80 - this denotes the percentage of all doctors that are in couples (default is 20% otherwise) 85 - this refers to a tie density of 0.85 AS - couples in this instance only accept assignments if both members are assigned the same hospital ML - this denotes the presence of a master list G5/G10/G25/etc i this denotes the number of distinct grades allowed in the master list ## File format Each file contains one instance, and both HRT and HRTC instances use the same format. The first line in each file denotes s, the number of single doctors in the instance. The next line denotes c, the number of couples in the instance, and the third line marks h, the number of hospitals in the instance. Following this, we have s+c lines with the doctors preferences. The first s lines are for each single doctor, where each line begins first with an identifier for the doctor (a number between 1 and s inclusive), and then a space separated list of the preferences of the doctor in descending order of preference. The next c lines give the preferences for the couples. Note that for couples, each line begins with two identifiers (one for each doctor) and then is followed by some number of pairs of integers. These preferences should be read two at a time. For instance, the line 17 19 3 3 2 2 indicates a couple whose doctors are identified as 17 and 19. The top preference of this couple is for both members to be assigned to hospital 3, and the second preference of this couple is for both members to be assigned to hospital 2. Following the preferences for couples, we have h lines marking the hospitals' preferences. These begin with an identifier, which is followed by the capacity of the hospital, and then the preferences of that hospital over individual doctors. A hospitals' preference list may include ties, which are marked by brackets, and note that a hospital does not have preferences for the couple as a pair, but for the individual members of the couple. # Solutions.zip The folders in this zipfile each contain the experimental output from running various instances through various codes on our server cluster. This output mostly pertains to the performance (runtimes etc.) of the codes. The output comes in two formats, depending on the exact experiment being run. For the codes E_MM, F_BIS, G_KPR, H_PLUS, we measured fewer parameters. Each file in those folders corresponds to an experiment (often completed over a set of instances). The filenames are used to describe the instances whose details are kept within the file. These filenames may have the following strings within them: SEPARATE - indicates that couples may be separated 750_750_50_10_10 - indicates that we have 750 doctors, 750 positions spread across 50 hospitals, with single doctors and doctors in couples having preferences of length 10 (Note that the exact numbers vary between instances, and that a couple has a preference list of 10*10 if each doctor in the couple has a preference list of length 10) ML - indicates that the preferences of the hospitals are derived from a master list ML_10 - indicates that the preferences of the hospitals are derived from a master list, and that the hospitals are given a score in the range [1,10] that determines the preference lists of the doctors (sometimes seen as ML_2 for small instances) _85 - The tie density of the hospitals (i.e., the hospitals' preference lists have ties) AS - These are instances where couples only find acceptable placements where they both are assigned the same hospital G500 - the instance uses 500 (variable) distinct scores to create a master list of the doctors P40 - 40% (variable) of the doctors are in couples M4 - The capacity of each hospital is reduced by 4 (variable, Minus 4) P3 - The capacity of each hospital is increased by 3 (variable, Plus 3) As mentioned earlier, the contents of the files depends on the experiments run. For directories E_MM, F_BIS, G_KPR, and H_PLUS, the files contain the following information in tab-separated columns: The instance name 1 if an optimal solution was found, 0 otherwise total runtime runtime spent before solving starts lower bound upper bound number of variables number of constraints number of non-zeroes in the coefficient matrix % of single doctors not assigned % of couples not assigned tie density For all other directories, the files contain the following information in tab-separated columns: The instance name 1 if an optimal solution was found, 0 otherwise total runtime runtime spent before solving starts lower bound upper bound linear relaxation number of variables number of constraints number of non-zeroes in the coefficient matrix linear relaxation after solver preprocessing number of variables after solver preprocessing number of constraints after solver preprocessing number of non-zeroes in the coefficient matrix after solver preprocessing average rank of the assigned hospital for single doctors standard deviation of the rank of the assigned hospital for single doctors % of single doctors not assigned worst rank of the assigned hospital for single doctors average rank of the assigned hospital for couples standard deviation of the rank of the assigned hospital for single doctors % of couples not assigned worst rank of the assigned hospital for couples average worst rank of doctor assigned to hospitals with at least one doctor assigned standard deviation of worst rank of doctor assigned to hospitals with at least one doctor assigned % of hospitals with no assigned doctor worst rank of doctor assigned to hospitals with at least one doctor assigned tie density