This is the user manual for the Matching Algorithm Toolkit. It explains how to use the different available menus. To go back, click here!


Problem Class Selection
Here the user must select which problem class they are interested in working with. Problem classes that are currently supported include House Allocation, Hospitals/Residents, Stable Roommates, or Student-Project Allocation. Note that instances of the Stable Marriage problem are automatically recognized if submitted as input to the Hospitals/Residents problem. For more information about these problem classes, see Algorithmics of Matching Under Preferences, by David Manlove, World Scientific, 2013.


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.

Guidance on the required input format and parameter descriptions are provided below.


Parameter Guide
If the automatic random instance generator is selected, you will have a variety of parameters to configure. Some are trivial, others are described below. Note that only single instances yield the full output. Multi-instance inputs only yield summary statistics.

For House Allocation,

For Hospital Residents,

For Stable Roommates,

For Student-Project Allocation,



Required Instance Formats
If custom input is selected (either through upload or textbox), the following formats are required. All problem classes can take input with or without IDs in the agent preference lines, but the decision must be coherent between agent types. For example, if student preference lines are started with student IDs in a SPA instance, then lecturers and project lines must also be started with IDs. Otherwise, none of them can have IDs. For historic reasons, the HA and SR descriptions below talk about instances without IDs and the HR and SPA descriptions about instances with IDs.

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
For a full list of algorithms and when they are active, please refer to this table.

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
Once you have successfully executed an algorithm, you will be presented with the results panel. Here, the results of each algorithm you ran will be presented in a separate tab. The results can be textual and/or graphical.


Saving
There are three options for 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


Acronyms


Reporting Bugs
If you spot any issues with the application, please send a bug report to David Manlove.