Informal proof that the MIP solver is a minimum weight max?

[cczhu]

The Hungarian algorithm returns a minimum cost perfect matching (every node has a degree of 1) on a complete bipartite graph (complete means any top node is connected to every bottom node) where the number of top and bottom nodes is identical (in our case this would mean equal number of drivers and passengers). In cases where the graph is imbalanced (eg. for more drivers than passengers), we can generate dummy nodes with zero cost connections to valid nodes. We can then run the Hungarian Algorithm on this augmented graph, then remove the dummy nodes and any solution edges incident to them. Hanna et al. 2016 points out the solution is a minimum cost maximal matching, since not every node is used (eg. some drivers are not assigned) but if any more edges are selected the solution would not be a matching.

My mixed-integer programming problem finds a solution to the following:

1. Maximize the sum of weights. Weights are determined from max_travel_time_in_graph - travel_time, meaning that maximizing the weights is equivalent to minimizing the aggregate travel time.
2. If a pick-up cannot be connected with a drop-off, np.nan is used in the corresponding cost matrix element, and not included in the MIP problem.
3. Each drop-off is assigned at most 1 pick-up.
4. Each pick-up is assigned at most 1 drop-off.

The last two criteria constrain the solution to be a matching (with number of elements equal or fewer than the maximum cardinality). The first criterion can be argued to be a minimum aggregate travel time maximal matching since:

• If there is a free pick-up with a feasible link to a free drop-off, the link can be selected without affecting the rest of the solution. Its edge weight will simply add to the sum of weights, so including this free edge is always favourable. Therefore the algorithm will pick up free links until adding a new link will violate condition 3 or 4. Therefore the algorithm produces a maximal matching.
• By definition the solution maximizes the sum of weights, equivalently minimizing the travel time.

Note that trying to minimize the sum of weights given criteria 3 and 4 will lead to a solution of zero links.

This "sketch of a proof" might have holes in it, so I should check it (or ask someone who knows graph theory) before uploading it to the wiki or adding it to the documentation. For now, I'll name the MIP matching algorithm MinWeightMaximalLinker, and write docstrings assuming the above is correct.