Matchmaker

Concept

Concept

The simpleor matchmaker problem solves a well known problem in literature generally referred to as ‘maximum matching’.

In a graph \(G = (V, E)\) of Vertices and Edges, where each edge \(e \in E\) has a weight \(w(e)\), the goal is to find pairs of nodes such that the sum of the weights of the chosen edges is maximized. A node can only be connected to one other node at most.

If that sounded confusing, think of it this way:

Suppose you are the owner of a dating platform. After a round of speed dating, every member of your community expresses how much they would like to see the other person again. For instance, if there are three community member Alberto, Britta, and Charly, then Alberto rates Britta and Charly, B rates A and C, and C rates A and B. This can also be represented with a matrix \(A\), where element \(A_{i,j}\) corresponds to the rating person \(i\) gives to person \(j\).

For instance, suppose now

\[\begin{split}A = \begin{bmatrix} 0 & 6 & 1 & 2\\ 8 & 0 & 1 & 1\\ 0 & 2 & 0 & 10\\ 2 & 3 & 7 & 0\\ \end{bmatrix}\end{split}\]

Our job is to make pairs of people (no triplets, no singletons) such that the community as a whole is as happy as possible. It is allowed to leave people without a pair.

From \(A\) we can see that person 1 really likes person 2 (rating of 6), but is not really into person 3 and 4 (rated 1 and 2). Also person 2 is into person 1 (rating 8). Similar story for the pair 3 and 4: they like each other, but not person 1 and 2.

Also note that we put zeros on the diagonal to avoid pairing people with themselves.

In this case, we would like to match person 1 to 2 and 3 to 4. This may seem trivial in this example, but imagine having a community of 1000 people!

Usage

Usage Solver

Still on my todo list :)

Usage Generator

Still on my todo list :)

Code

Code

class simpleor.matchmaker.MatchMaker(match_matrix: numpy.array)

Class to solve matchmaker problems

Args:

match_matrix (np.array): square integer matrix indicating the reward

of assigning two nodes

class simpleor.matchmaker.MatchMakerProblemGenerator(n: int, edge_probability: float, minimum_value: int, maximum_value: int)

Class to generate a matchmaker problem

Args:

n (int): number of nodes of the matchmaker problem edge_probability (0 < float < 1): probability of generating a nonzero

element of the match_matrix. For small edge_probabilities, there are only few potential matches in the matchmaking problem. Vice versa for large edge_probability.

minimum_value (int = 0): minimum value of the matrix’ entries maximum_value (int = 1): maximum value of the matrix’ entries

generate()

Generates the match_maker_matrix based on sampling.

First, it samples an (n, n) matrix of integers between minimum_value and maximum_value. Then, every sampled element can still be set to zero based on a bernoulli draw with parameter edge_probability.

Sets:

match_matrix (np.array): matrix of size (n, n) of randomly generated

integers between minimum_value and maximum_value (zeros on the diagonal).

simpleor.matchmaker.do_match_maker_experiment(experiment_id: str, n_list: List[int], edge_probability_list: List[int], repeat: int, minimum_value: int = 1, maximum_value: int = 10, solver_list: list = ['pulp', 'heuristic'], save_result_directory: str = '/home/docs/checkouts/readthedocs.org/user_builds/simple-or/envs/latest/lib/python3.8/site-packages/data', save_problem_and_solution: bool = False)

Does a match_maker experiment and write results to a json file.

You can run this function to test the performance of the match_maker solver. For each combination of ‘n’ and ‘edge_probability’ the function generates a match_maker problem ‘repeat’ times, and solves it with all solvers specified in the ‘solver_list’.

Args:

experiment_id (str): identifier of the experiment n_list (list of ints): list of how many nodes in per matchmaker problem edge_probability_list: list of probabilities of generating an

edge between two nodes

solver_list (list of strings): ‘pulp’ and/or ‘heuristic’,

which solvers should be used to compute results

repeat (int): number of times a combination of the variables that describe

a matchmaker problem (n, edge_probability) should be repeated in the experiment

minimum_value (int, default 1): minimum value of element in match_matrix maximum_value (int, default 10): maximum value of element in match_matrix save_result_directory: str of a path save_problem_and_solution: bool

if true, saves the love_matrix and solution matrix

simpleor.matchmaker.get_full_match_maker_solution(match_maker: simpleor.matchmaker.MatchMaker, solver: str) → Tuple

Get objective value, solution matrix, and solution status

Args:

match_maker (MatchMaker): solver MatchMaker instance solver (str): solver (pulp/heuristic)

Returns:

Tuple(objective value, solution matrix, solution status)