# Building the Model Using NetworkX

After we obtained the pij matrix, we had the satisfaction level between each advisor and each student. Therefore, the next step is to build the proper model and match them.

we construct the model based on the linear programming of Operation Research, the raw model is mentioned in the abstract (http://ccsummerresearch.blogs.wm.edu/2018/04/16/mathematical-model-maximizing-matching-rate-students-advisors/), and we adjusted it based on the goal of this project.

First, student i is assigned to professor j, and the parameter is ranged from -400 to 14 as mentioned in previous post; xij is designed to be a binary variable (xij=1 if student is assigned to a desired advisor and 0 otherwise); parameter dj is the demand of professors. We want to maximize the total satisfaction degree of both advisees and advisors, which is the product of pij and xij ; but there are restrictions, like “each student can only have one advisor”, and each advisor has their upper bound, we are subject to; finally, the variables cannot be nonnegative. Therefore, combining all these factors together yields the following Linear Programming formulation: This is the linear programming formulation, but since our data contains 1615 students and 343 advisors, we need to generalize a system to do the calculation for us and coding all information. Therefore, we choose the NetworkX as the tool for final matching. NetworkX is a Python package for the matching and manipulation of the structure, dynamics, and functions of complex networks. Since we already obtained the pij matrix, the only thing left is to generate best matching, i.e., maximize the value of pij x xij.

The first thing of using NetworkX is to create a “graph”.  Imagining there is a big graph, and both students and advisors are “nodes” on the graph. “Student” nodes are on one side and “advisor” nodes are on another side. The matchings between students and advisors have “direction” because advisors have  “supply” and students have “demands”. So the direction is from advisors to students.

In addition, each node is linked by “edge”, and each edge has its own “capacity” (in our case, number of advisor a student demanded, which is 1) and “weight” (the pij, satisfaction degree). Since the NetworkX is used to minimize the outcome, and we want to maximize the outcome, so we used it to minimize the negative satisfaction level. For example, in this case, a1 will more likely to match to s1614, since the weight is -6.75, which is smaller than -3.5. This means the pij value between a1 and s1614 is higher than that between a1 and s1.

Before running the NetworkX, another important thing is that, for NetworkX, the demand and supply should be equal. However, in our case, we have 1615 true students and 1631 true slots (sum of demands of all advisors). So we should first equate the number of demands and supplies.

1. The pre-matched students will have demand 0 and supplies of corresponding advisor will -1.
2. In addition, we create a ” student dummy” to take care of the left slots. In our case, we have 1631-1615 = 16 left slots, so the “sdummy” will have a capacity of 16. 