Within this Github repo, we (Siyu Wang, Rongxi Yi, ZiYang Xu) implemented the Hospital-Doctors matching problems both in the hospital don't have a perference case (standard question) and the hopitals have prefernce cases (the challenge question). Each cases is solved by using MCMF and NRMP algorthims respectively.
To make a better user experience, an UI interface is implemented (Operation is manuel is explained in Section I). A detailed algorthim explaination is further summarized in the min_cost_flow.ipynb file and in Section II of the readme.md file.
NOTICE that the UI interface is a shared structure between MCMF and NRMP algorithm. If performing MCMF task, please open main_Assignment of doctors.py and run. If performing NRMP task please open Main_NRMP.py file and run.
- Number of Doctors in spinbox: an integer
- Number of Hospitals in spinbox: an integer
- Each doctor's perference in the chart: every row is a ranking of hospitals according doctor's perference, put an integer (smaller than the number of hospital) in each blank
- Hospital capacity: put an integer in the blank under each hospital
Number of doctors: 5
Number of hospitals: 3
doctor 1's preferences: 1 2 3
doctor 2's preferences: 2 1 3
doctor 3's preferences: 3 2 1
doctor 4's preferences: 1 2 3
doctor 5's preferences: 2 1 3
hospital 1's capacity: 2
hospital 2's capacity: 3
hospital 3's capacity: 2
- run: click the
runbutton, run the algorism and output the assignment in textBrower - drow: click the
drowbutton, get the treelist and graph in output window
- Tree List: a list which can fold or unfold a class of assignment
- Dot Gragh: a gragh which includes nodes of hospitals/doctors, and edge indicating the assignment
- Change node color: Three colors to change,
default,skyblueorred - Change output_to_local option: Two options to switch,
listorgraph - Output to local: click the
output to localbutton and input the filename and filelocation in dialog
- Number of Doctors in spinbox: an integer
- Number of Hospitals in spinbox: an integer
- Each doctor's perference in the chart: every row is a ranking of hospitals according doctor's perference, put an integer (smaller than the number of hospital) in each blank
- Each Hsopital's perference in the chart: every row is a ranking of doctors according Hsopital's perference, put an integer (smaller than the number of doctor) in each blank
Number of doctors: 5
Number of hospitals: 2
doctor 1's preferences: 1 2
doctor 2's preferences: 1 2
doctor 3's preferences: 1 2
doctor 4's preferences: 1 2
doctor 5's preferences: 1 2
hospital 1's preferences: 1 2 3 4 5
hospital 2's preferences: 5 4 3 2 1
- run: click the
runbutton, run the algorism and output the assignment in textBrower - drow: click the
drowbutton, get the treelist and graph in output window
- Tree List: a list which can fold or unfold a class of assignment
- Dot Gragh: a gragh which includes nodes of hospitals/doctors, and edge indicating the assignment
- Change node color: Three colors to change,
default,skyblueorred - Change output_to_local option: Two options to switch,
listorgraph - Output to local: click the
output to localbutton and input the filename and filelocation in dialog
Reboot: reboot the program, put the mouse on the yellow button at top right corner of the window and you will see the hintMinimize: minimize the window, put the mouse on the gray button at top right corner of the window and you will see the hintMaximize and Restore: maximize the window and restore to a normal one when maximized, put the mouse on the green button at top right corner of the window and you will see the hintClose: close the window and end the program, put the mouse on the red button at top right corner of the window and you will see the hint
A window of warning will pop up if there is not parameter in the running process.
eg. you change a node color in output window but you haven't input any parameter or haven't run the algrorithm yet.
We support the following assignment tasks that are common in the healthcare systems.
- Each Doctor
needsto find a hosptial. - Each Doctor has a
ranked preference listcontaining every hosptial. - hosptials don't have preferences over doctors.
- The
maximum capacityof each hospital varies.
The total capacity exceeds the number of doctors.
As shown in the figure below, circles ○ representing doctors, and triangles △ representing hospitals.
The problem can be modeled into a bipartite graph, which means that vertices are separated into two sets and vertices in the same set has no connections between each other.
doctor No.1 has a level of preference towards hospital No.1, hospital No.2, and hospital No.3. This can be represented as three different edges pointing from doctor No.1 to each hospital, as shown in the figure below.
Each doctor has a level of preference towards each hospital. Now the problem can be represented as the figure below.
What we need to find out is that, what is the most satisfying arrangement when ensuring every doctor can find a hospital.
- We can translate
most satisfyingintoleast cost, where the cost is the preference ranking. If a doctor rank a hospital as their favorite, the rank value is the smallest, which can be used as a cost. We set the cost of each edge as the preference ranking. - Also, we can translate
every doctor can find a hospitalintomaximize the matching number, which can be translated intomaximize flow under certain restrictions. Since that each person is ONE doctor and can only take 1 capacity of a hospital, we set the flow capacity of each edge as 1. - For example, if doctor No.1 likes hospital No.1 the most, hospital No.2 the second, and hospital No.3 the least, the costs and flow capacities of doctor No.1's edges are as below. (Edge: flow_capacity (cost) )
- Add a starting point
Sand connect it with every doctor point. We set the flow capacities of these edges as 1. This way, a doctor can maximumly choose one hospital. - Add a ending point
Eand connect it with every hospital point. We set the flow capacities of these edges as each hospital's capcities. This way, a hospital can maximumly take in their capacity amount of doctor. - Set the costs of all starting and ending edges as 0. This way, only doctor' preferences towards hospital can contribute to costs.
The problem is now a minimum cost maximum flow problem.[3] The algorithm follows the below flowchart. It searches for the least-cost path in all the paths that still have left some flow capacities, and fills the path with maximum flow. The algorithms repeats itself until there is no more available path.
We support the following assignment tasks that are common in the healthcare systems.
- Each doctor
needsto find a hospital. - Each doctor has a
ranked preference listcontaining every hospital. - Each hospital has a
ranked preference listcontaining every doctor.
As shown in the above flowchart. Each match is a combined result both from the doctors and the hospital's perference.[4] In such a way the final matching result represents the optimal solution.
References:
[1] Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993). Network Flows. Theory, Algorithms, and Applications. Prentice Hall.
[2] Moore, Edward F. (1959). "The shortest path through a maze". Proceedings of the International Symposium on the Theory of Switching. Harvard University Press. pp. 285–292.
[3] Duan, Fanding (1994), "关于最短路径的SPFA快速算法 [About the SPFA algorithm]", Journal of Southwest Jiaotong University, 29 (2): 207–212
[4] P. A. Nagarkar and J. E. Janis, “Fixing the ‘match’: How to play the game,” Journal of Graduate Medical Education, vol. 4, no. 2, pp. 142–147, 2012.