The minimum cost perfect matching problem is formally defined as an optimization problem where:
- The set of instances is the set of all edge-weighted undirected graphs $G=(V, E, w)$, where $w : E \to \mathbb{R}$.
- Given an instance $G=(V, E, w)$, the set of feasible solutions are the perfect matchings $M$ of $G$, i.e., all the sets $M \subseteq E$ such that, $\forall u \in V \; |M \cap \{ (u, v) \in E : v \in V \}| = 1$.
- Given an instance $G=(V, E, w)$ and a feasible solution $M$ for $G$, the is a function called measure defined as $m(G, M) = \sum_{e \in M} w(e)$.
- The measure is to be minimized.
As for the problem making sense... the problem is abstract in nature and it can be perfectly well-defined without any need for vertices, edges, weights or the matching itself to represent anything.
Of course it is fairly easy to come up with (mock) scenarios in which you might want to compute a minimum cost perfect matching of a suitable graph that is modelling some real-world entities, e.g., the one that follows.
You are organizing a trip for a (large) group of $n=4k$, $k \in \mathbb{N}^+$, participants that will travel together on a bus with $n$ seats. Bus seats are arranged in rows of $4$, with $2$ adjacent seats on each side and a corridor in the middle.
Not all of the participants enjoy their company equally (indeed, some of them categorically refuse to be close by) and you know, for each pair of people that can sit together, how much they'd happy (or unhappy) to be sat next to each other (say, in a scale from $-1$ to $1$).
Being a thoughtful organizer, you want to arrange seats in order to maximize the social welfare of the participants, i.e., the sum of the happiness of all pairs of neighbors in the arrangement you choose.
