Minimum-Weight Perfect Matching¶

Definition¶

In the CPP construction, a minimum-weight perfect matching pairs the odd-degree vertices so that each belongs to exactly one pair and the sum of pair costs is minimized. The cost $d_{ij}$ of a pair is its shortest-path distance. With a binary variable for each unordered pair,

\begin{gathered} \min\sum_{i<j}d_{ij}x_{ij},\\ \sum_{j<i}x_{ji}+\sum_{j>i}x_{ij}=1\quad \text{for each odd vertex }i. \end{gathered}

Interpretation¶

The matching decides which odd vertices should be linked by duplicated paths in the Chinese postman construction. Each odd vertex needs exactly one partner, and the total extra length should be as small as possible.

Three copies of four odd vertices P, Q, R and S: the shortest-path distances between them, the cheapest perfect matching PQ and RS with weight 9, and a dearer matching with weight 11.

The left panel gives the shortest-path distances between the four odd vertices $P,Q,R,S$ . Four vertices can be paired in three ways: $\{PQ,RS\}$ costs $4+5=9$ $9$ , $\{PS,QR\}$ costs $6+5=11$ $11$ , and $\{PR,QS\}$ costs $6+7=13$ $13$ . The middle panel shows the cheapest pairing, of weight 9.

Perfect means that every odd vertex lies in exactly one pair; this is the constraint that sets the sum of the variables at vertex $i$ equal to $1$ . Minimum-weight refers to the objective $\displaystyle \sum d_{ij}x_{ij}$ . A perfect matching always exists here, because the number of odd-degree vertices is even (see vertex degree). Each pair cost is a shortest-path distance rather than the length of a direct edge, since the duplicated route may pass through other vertices.

Pairing must be optimized jointly, since a locally cheap pair may leave expensive remaining pairs. On a line $P-Q-R-S$ with edge lengths $2,1,2$ , taking the closest pair $Q,R$ first (cost 1) forces $P$ with $S$ (cost 5), a total of 6, whereas $\{PQ,RS\}$ costs $2+2=4$ $4$ . This is why the choice is written as a binary integer program, as in the Definition. Matchings return later in the course with two separate groups of vertices, in bipartite matching.

Key Results¶

Each pair variable is binary.
For four odd vertices there are three complete pairings to compare.
This is a nonbipartite matching problem because the vertices are not separated into two assignment groups.

Examples¶

For the illustrated four odd vertices, the alternative pairing $\{PR,QS\}$ costs 13. The minimum-cost pairing determines which shortest paths are duplicated in the CPP construction.

The pairings AB/DE, AD/BE, and AE/BD cost 8, 7, and 8.
The optimum selects $x_{AD}=x_{BE}=1$ $1$ .

Prerequisites¶

Sources¶

OR Modelling · Week 4

Aliases: minimum-cost perfect matching Symbols: sum

Last updated: 22 October 2026 19:04