Why Put Restrictions Inside the Matching Problem?
An optimal pair-matching algorithm minimizes total distance across the selected treated-control pairs. But a low-distance solution is not necessarily acceptable for a study design: a pair may violate a required exact match, a specific pair may be disallowed, or the solution may use the wrong number of units. The key principle is to encode these requirements in the optimization problem itself, rather than find an unrestricted solution and try to repair it afterward.
This tutorial considers one-to-one matching without replacement: each selected treated unit is paired with one control, and no unit appears in more than one pair. The number of pairs is fixed in advance. Restrictions determine which pairs can be selected; the objective chooses the lowest-cost feasible allocation. These are design choices. Finding a feasible, low-cost allocation does not by itself establish that a later treatment-effect estimate has a causal interpretation.
Writing the Constraints
The standard one-to-one assignment constraints are \( \sum_{j\in C}x_{ij}\leq 1\) for every treated unit and \( \sum_{i\in T}x_{ij}\leq 1\) for every control unit. To select exactly \(K\) pairs, require \( \sum_{i\in T}\sum_{j\in C}x_{ij}=K\). Since each selected pair contains one treated and one control unit, this selects exactly \(K\) units from each group. The objective is to minimize the sum of the selected pair costs.
The binary restriction matters: it makes each potential pair either selected or not selected. The at-most-one constraints prevent reuse, and the equality fixes the match count. A solution is optimal only among allocations satisfying all these conditions; it need not be the lowest-cost allocation if the restrictions are ignored.
For exact matching on a categorical covariate, a treated-control pair is eligible only when the two units have the same required category. One convenient formulation is to define an eligible-pair set \(E\subseteq T\times C\) containing only pairs that meet all exact-match requirements, and optimize over \(E\). A pair can likewise be removed from \(E\) when it is specifically forbidden for another design reason. Equivalently, the corresponding variable can be fixed at zero. If a design requires prescribed numbers of pairs in particular strata, those requirements need their own constraints; merely allowing within-stratum pairs does not impose stratum-specific quotas.
Worked Example: Exact Matching and a Forbidden Pair
Suppose three hypothetical treated units, A, B, and C, and four controls, u, v, w, and x, are classified as North or South. A and C are North; B is South. Controls u and v are North; w and x are South. The design requires exactly two pairs, exact matching on region, and forbids pair A-u. The eligible costs are:
| Treated unit | Eligible control and cost |
|---|---|
| A (North) | v: 5 |
| B (South) | w: 1; x: 4 |
| C (North) | u: 3; v: 2 |
The exact-match rule removes every cross-region pair. The additional prohibition removes A-u, leaving the eligible pairs shown. The required number of pairs is \(K=2\), so the objective is the sum of the two selected costs, with no treated or control unit reused.
Selecting B-w and C-v is feasible: both pairs match within region, the units are distinct, and \(1+2=3\). To check that this is optimal, consider the choices. If B is used, its cheapest eligible pair is B-w, cost 1. The cheapest compatible second pair is C-v, cost 2, giving total 3; A-v would cost 5 instead. If B is not used, two North pairs must be formed from A and C, but they cannot both use v, and A has no other eligible control. Thus two such pairs cannot be made. The minimum feasible total cost is therefore 3, using B-w and C-v.
Unit A remains unmatched. That is allowed because the specification fixes two pairs, not the identity of the two treated units that must be selected.
Feasibility Comes Before Optimality
A constrained problem can have no solution. For example, \(K\) cannot exceed the number of treated units, the number of controls, or the maximum number of pairs that can be made using eligible edges without reusing units. Restrictions can make that maximum smaller than either group size. A solver reporting infeasibility is not reporting a poor optimum: it means no allocation meets all the stated conditions.
A useful diagnostic is to represent eligible pairs as edges in a bipartite graph: treated units are on one side, controls on the other, and an edge joins units that are allowed to match. A matching is a set of edges with no shared endpoints. The question for fixed \(K\) is whether this graph contains a matching with at least \(K\) edges. If it does, a subset of exactly \(K\) edges gives the required match count. If it does not, no distance-minimizing procedure can satisfy the specification.
For example, when every treated unit must be matched, a standard feasibility condition is Hall’s condition: for every subset \(S\) of treated units, the set of controls connected to at least one unit in \(S\) must contain at least \(|S|\) controls. For a general fixed \(K\), a maximum-cardinality bipartite matching or a corresponding assignment solver can check feasibility directly. Inspecting each unit’s available partners is useful, but it is not sufficient: several units can each have a potential partner while competing for the same small set of controls.
Worked Example: Restrictions Leave Too Few Distinct Controls
Consider two hypothetical treated units, A and B, and two controls, 1 and 2. The design requires \(K=2\). After applying the restrictions, the only eligible pairs are A-1, A-2, and B-1. Suppose their costs are 2, 4, and 3, respectively.
Each treated unit has at least one eligible control, but that alone does not guarantee two pairs. If A is assigned to control 1, B has no eligible unused control. If A is assigned to control 2, B can be assigned to control 1, giving two pairs at total cost \(4+3=7\). Thus the problem is feasible, and its only feasible two-pair allocation has cost 7.
Now add a restriction forbidding A-2. The eligible edges become A-1 and B-1. Both treated units still have a potential partner, but the only available control is 1. At most one pair can be formed, so a requirement of two pairs is infeasible. No objective calculation can fix this conflict; the design must change, for example by relaxing a restriction or reducing \(K\), if either change is substantively acceptable.
Why the Unrestricted Optimum Cannot Simply Be Repaired
The constrained optimum is not generally obtained by first solving the unrestricted problem and then deleting invalid pairs. Deletion can leave fewer than \(K\) pairs, reuse conflicts can emerge, and the remaining allocation may not be the cheapest feasible one. Even when an unrestricted solution has the right number of pairs, it may favor pairings that the design explicitly rules out.
Worked Example: Exact-Match Rules Change the Optimum
Suppose treated unit A is in category X and treated unit B is in category Y. Control 1 is in X and control 2 is in Y. The hypothetical costs are A-1: 1, A-2: 2, B-1: 1, and B-2: 100. The requirement is to match both treated units, so \(K=2\).
Without exact matching, there are two complete allocations. A-1 with B-2 costs \(1+100=101\). A-2 with B-1 costs \(2+1=3\), so the unrestricted optimum is the second allocation. But both of its pairs cross categories and violate the exact-match rule.
Under exact matching, only A-1 and B-2 are eligible. They use distinct controls and match within category, so they form the only feasible allocation. Its total cost is \(1+100=101\). The high cost does not mean the constrained algorithm failed: it reflects the trade-off imposed by the stated design restriction. If that cost is unacceptable, the response is to reconsider the design specification, not to describe the invalid cost-3 allocation as a constrained solution.
Solving, Diagnosing, and Comparing Approaches
Once the eligible-pair set and required match count are explicit, solve the resulting assignment problem and inspect the selected pairs. For small problems, enumeration can verify a solver’s output; for larger problems, standard assignment or integer-optimization algorithms are appropriate. The justification for the formulation is direct: every feasible one-to-one allocation corresponds to a binary vector satisfying the constraints, and every binary vector satisfying them describes a feasible allocation. Minimizing the sum of selected costs therefore selects the least-cost allocation within the design’s feasible set.
Check the result against the design, not only against its objective value. Confirm that:
- the number of selected pairs is \(K\), with \(K\) distinct treated units and \(K\) distinct controls;
- every selected edge satisfies all exact-match requirements and is not forbidden;
- no unit appears in more than one pair; and
- the reported objective equals the sum of the selected pair costs.
If infeasibility is reported, inspect the eligible-pair graph and identify whether the problem is a too-large \(K\), an empty set of eligible partners for some required unit, or competition among units for the same controls. If feasible solutions exist but have unexpectedly high total cost, inspect the restrictions and the costs separately. A high constrained cost can be a genuine consequence of the restrictions; it can also expose a coding error, such as accidentally forbidding an intended pair or using the wrong distance.
Compared with unconstrained optimal matching, the constrained formulation can meet explicit design requirements but may increase total cost or leave more units unmatched. A greedy nearest-neighbor procedure makes local choices and can also produce a higher total cost than the optimal feasible allocation. Exact matching can be implemented as an edge-eligibility rule here; its defining feature is that cross-category pairs are excluded, not that the remaining allocation is automatically optimal. In every comparison, the objective and the feasible set should be reported separately: a smaller cost is meaningful only when the candidate allocations meet the same design requirements.
Restrictions have limits. Exact matching on many covariates can sharply reduce the eligible-pair set, and fixed \(K\) may become impossible. Even a feasible allocation can have poor overall covariate balance on characteristics not constrained by the matching rules. Constrained optimal pair matching optimizes the specified cost subject to the specified rules; it does not guarantee balance on every variable, repair poor overlap, or remove bias from unmeasured confounding. The restrictions and the consequences of any unmatched units therefore require substantive scrutiny.
Check Your Understanding
Answer each question, then compare with the solutions below.
- In one-to-one matching without replacement, what do the at-most-one constraints enforce?
- There are 8 treated units and 5 controls, and the design requires \(K=6\) pairs. Can the problem be feasible? Explain.
- With \(K=2\), the eligible edges are A-1, A-2, and B-1. Is a two-pair matching feasible? Give one if so.
- Why is an unrestricted minimum-cost solution not necessarily an acceptable constrained solution?
Solutions. (1) Each treated unit and each control can appear in at most one selected pair, preventing reuse. (2) No. Each pair uses a distinct control, so at most 5 pairs can be formed; \(6>5\). (3) Yes: select A-2 and B-1. These edges have no shared endpoint, so they form two distinct pairs. (4) It may include a forbidden or non-exact pair, or otherwise violate a design constraint. The minimum must be found over allocations that satisfy all restrictions, not over the larger unrestricted set.