Problem Class Selection

Input Selection

Once you have selected a problem class, you will have to choose the instance/instances you want to work on.

There are currently three available options:

**1. File based input:** You will be prompted to select an input file that matches the problem class specific instance format.

**2. Automatically generated input:** You will be provided a form to specify problem-specific parameter values.

**3. Textbox input:** You will enter an instance directly into a textbox which matches the problem class specific format.

Parameter Guide

#### For House Allocation,

**Probability of Ties:**ties in the preferences of applicants over houses**Minimum/Maximum Preference List size:**restrictions on preferences of applicants over houses**House popularity skewness:**skewness affects the probability that a given house will be chosen from those remaining with the most popular house being k times as likely as the least popular house (for skewness factor k), and the other houses linearly distributed in between**Even position distribution:**boolean whether positions should be equally or randomly distributed to houses

#### For Hospital Residents,

**Probability of Ties (Hospitals):**ties in the preferences of hospitals over residents**Probability of Ties (Residents):**ties in the preferences of residents over hospitals**Minimum/Maximum Preference List size (Residents):**restrictions on preferences of residents over hospitals**Hospital popularity skewness:**skewness affects the probability that a given hospital will be chosen from those remaining with the most popular hospital being k times as likely as the least popular hospital (with skewness factor k), and the other hospitals linearly distributed in between**Resident popularity skewness:**skewness affects the probability that a given resident will be chosen from those remaining with the most popular resident being k times as likely as the least popular resident (with skewness factor k), and the other residents linearly distributed in between**Even position distribution:**boolean whether positions should be equally or randomly distributed to hospitals

#### For Stable Roommates,

**Probability of Ties:**ties in the preferences of roommates over each other**Preference List Density:**fraction of other roommates that appear in a roommate's preference list

#### For Student-Project Allocation,

**Even position distribution:**boolean whether lecturer and project capacities should be equally or randomly distributed to lecturers and projects, respectively**Min/Max student pref length:**restrictions on preferences of students over projects**Student skewness:**skewness affects the probability that a given student will be chosen from those remaining with the most popular student being k times as likely as the least popular student (with skewness factor k), and the other students linearly distributed in between**Project skewness:**skewness affects the probability that a given project will be chosen from those remaining with the most popular project being k times as likely as the least popular project (with skewness factor k), and the other projects linearly distributed in between**Probability of Ties (Students):**ties in the preferences of students over projects**Probability of Ties (Lecturers):**ties in the preferences of lecturers over students

Required Instance Formats

#### For House Allocation,

the first line contains two numbers separated by a space - the first one, x, indicates the number of applicants
and the second one, y, indicates the number of houses.

The next x lines are for the preference lists of the applicants. Each line contains the preferences of an applicant over the houses as a space separated list. After those lines, there are y lines that contain a single number - the capacity of the house represented by the line.
The following is an example contents of a HA input string:

3 2

1 2

1 2

2 1

2

1

We can see that there are 3 applicants and 2 houses.

Applicants 1 and 2 each prefer house 1 over house 2 while applicant 3 prefers house 2 over house 1.

House 1 has capacity 2, while house 2 has capacity 1.

#### For Hospitals/Residents,

the first line contains two numbers separated by a space - the first one, x, indicates the number of residents
and the second one, y, indicates the number of hospitals.

The following x lines are for the preference lists of the residents. The resident id is directly followed by a colon and a space, the preferences follow as a space separated list. Ties are represented by putting brackets around the preference entries.

.
The next y lines are for the preference lists of the hospitals. The hospital id is directly followed by a colon and a space, then the hospital's capacity, a colon and a space, and finally the preferences as a space separated list. Ties are represented by putting brackets around the preference entries.
The following is an example contents of an HR input string:

4 2

1: (2 1)

2: 2

3: (1 2)

4: 1

1: 1: (3 4 1)

2: 3: (3 2 1)

We can see that there are 4 residents and 2 hospitals.

The first resident has id 1 and does not prefer one hospital over the other due to ties.

The second resident has id 2 and only finds hospital 2 acceptable.

The first hospital has id 1, capacity 1, and no preference over the applicants due to ties.

#### For Stable Roommates,

the first line contains a single number - the number of roommates, x. The next x lines are the preference lists of each roommate over the remaining roommates. Ties are represented by putting brackets around the preference entries.
The following is an example contents of a SR input string:

4

3 2 4

1 4 3

2 1 4

3 1 2

We can see that there are 4 roommates.

The first roommate prefers roommate 3 over 2 and 4 and prefers roommate 2 over roommate 4.

#### For Student-Project Allocation,

the first line contains three numbers separated by a space - the first one, x, indicates the number of students, the second one, y, indicates the number of projects, and the third one, z, indicates the number of lecturers.

The following x lines are for the preference lists of the students. The student id is directly followed by a colon and a space, the preferences follow as a space separated list. Ties are represented by putting brackets around the preference entries.

The next z lines are for the preference lists of the lecturers. The lecturer id is directly followed by a colon and a space, then the lecturer's capacity, a colon and a space, and finally the preferences as a space separated list. Ties are represented by putting brackets around the preference entries.

Finally, the last y lines capture the project information. Each line starts with the project id followed by a colon and space, then the project capacity followed by a colon and space and finally the lecturer id who supervises the project.
The following is an example contents of an SPA input string:

4 3 2

1: 3 1

2: 1 2 3

3: 2 3

4: 3 2

1: 2: 2 3 1 4

2: 2: 3 4 2 1

1: 2: 1

2: 1: 2

3: 1: 2

We can see that there are 4 students, 3 projects, and 2 lecturers.

The first student has id 1 and prefers project 3 over project 1 and does not find project 2 acceptable.

The first lecturer has id 1, capacity 2, and prefers student 2 over 3 over 1 over 4.

Project 1 has capacity 2 and is supervised by lecturer 1.

Algorithm Selection

Once input has been provided, you will be given a list of algorithms to choose from. Select as many algorithms as you wish to run. Note that each algorithm has a short tooltip describing its operation.

Note that if no algorithms are presented, then there is no algorithm available that can solve the given instance.

Results

Saving

**1. Save Instances:** will save the input instances currently supplied to the program. This is good for saving randomly generated instances

**2. Save Current Results:** will save the results that are currently active on the screen. This is also the only way to save
graph output at this point.

**3. Save All Results:** will save all of the textual results that have been generated. Note that this will not save graphical output.

Note that option 1 is available only after input has been provided and options 2 and 3 are only available once results have been produced.

Contributors

- David Manlove
- Supervision and support on the projects
- Active development/maintanance
- Frederik Glitzner
- Making this web app more flexible and (user) friendly :)
- Extension app to SPA (logic, generators, models, ckecks, displays...)
- Original algorithm implementation of Tan-Hsueh and Maximum Stable Matching (SR)
- Porting of legacy algorithm code for student- and lecturer-optimal stable matching and greedy/generous/cost-optimal matching (SPA)
- Bug fixing, maintenance, consolidation of codebases, introduction of version control
- Frances Cooper
- Implementation of popular matching algorithms
- Visualisation of switching graph
- Susan Fairley
- Implementation of an algorithm for SMTI under strong-stability
- Implementation of a random instance generator for SM, SMI, SMT and SMTI problems
- Rob Irving
- Supervision and support on the projects
- Implementation of a random instance generator for HR and HRT
- Implementation of resident-oriented and hospital-oriented heuristics for MAX HRT
- Implementation of algorithms for finding profile-based optimal matching algorithms
- Augustine Kwanashie
- Visualisation of structures including rotation posets and Hasse diagrams and other modification to the front-end GUI
- Implementation of algorithms for finding all stable matchings for SRI and SMI
- Implementation of Kiraly's approximation algorithm for MAX HROST
- Implementation one-sided profile-based optimal SPA algorithms
- Development/maintanance
- Stephen Lavery
- Legacy Implementation of an algorithm for finding a student-optimal stable matching in SPA-S
- Legacy Implementation of a random instance generator for SPA
- Yiting Zhang
- Legacy Implementation of an algorithm for finding a lecturer-optimal stable matching in SPA-S
- Suiyi Yang
- Implementation of an algorithm for finding an SMI maximum popular matching
- Boris Lazarov
- Implementation of web application using Python / Django and Spring Boot
- Development/maintenance
- Andy Leitch
- Implementation of algorithms for HR and HRT under super-stability
- Zhiyuan Lin
- Greedy, Generous and Popular algorithms for CHAT problems
- Development/maintanance
- Ryan Mackinnon
- Implementation of Algorithm SMT-super
- Asim Mahmood
- Implementation of an algorithms for finding a popular matchings in HA
- Implementation of a random instance generator for HA
- Andrei Palade
- Developed web app version of toolkit using Google Web Toolkit
- Dimitar Petrov
- MAX HRT approximation algorithm for one-sided and two-sided ties by Kiraly
- William Pettersson
- Development/maintenance
- Aleš Remta
- Initial development of the matching toolkit
- Implementation of EGS algorithm for SMI and algorithm for maximum Pareto optimal matching in HA
- Colin Sng
- Implementation of an algorithm for finding a stable matching or reporting that none exists in SR
- Implementation of a random instance generator for SR
- Philip Yuile
- Implementation of the front-end GUI application
- Various modifications to random instance generators and wrapper classes
- Implementation of algorithms for finding profile-based optimal matchings in HAT and popular matchings in HA

**Acronyms**

- EGS - Extended Gale Shapley Algorithm
- HA - House Allocation Problem
- HAT - House Allocation Problem with Ties
- HRT - Hospitals/Residents Problem with Ties
- MAX HROST - Maximum Cardinality Stable Matching in the Hospitals/Residents Problem with one sided Ties
- MAX HRT - Maximum Cardinality Stable Matching in the Hospitals/Residents Problem with Ties
- SM - Stable Marriage Problem
- SMT - Stable Marriage Problem with Ties
- SMI - Stable Marriage Problem with Incomplete Lists
- SMTI - Stable Marriage Problem with Ties and Incomplete Lists
- SR - Stable Roommates Problem
- SRI - Stable Roommates Problem with Incomplete lists
- SPA - Student-Project Allocation Problem
- SPA-S - Student-Project Allocation with Lecturer preferences over Students
- SPA-ST - Student-Project Allocation with Lecturer preferences over Students and Ties

Reporting Bugs