A Worked Constrained Optimal Matching Problem

What Constrained Optimal Pair Matching Does

In one-to-one pair matching, each retained treated unit is assigned one control, and a control can be used at most once. An optimal assignment chooses the set of pairs that minimizes a prespecified total distance. A constraint can rule out a pair entirely—for example, because its distance exceeds a caliper or because a required design restriction is not met. The optimization then searches only among assignments that satisfy both the matching ratio and the prohibitions.

The distinction between cost and feasibility matters. A feasible pair may have a large cost but remain available to the algorithm; a forbidden pair is not available at any cost. The solution is the lowest-cost assignment among the feasible assignments, not the assignment with the smallest cost considered pair by pair.

Definition: Let \(T\) be the set of treated units and \(C\) the set of control units. For each treated-control pair \((i,j)\), let \(d_{ij}\) be its prespecified matching cost. Define \(x_{ij}=1\) if treated unit \(i\) is matched to control \(j\), and \(x_{ij}=0\) otherwise. For one-to-one matching that retains every treated unit, the objective is to minimize \(\sum_{i\in T}\sum_{j\in C} d_{ij}x_{ij}\), subject to \(\sum_{j\in C}x_{ij}=1\) for every \(i\in T\), \(\sum_{i\in T}x_{ij}\leq 1\) for every \(j\in C\), \(x_{ij}\in\{0,1\}\), and \(x_{ij}=0\) for every forbidden pair. The fixed match ratio is one control per treated unit.

If the numbers of treated and control units are equal and every treated unit is retained, the constraints imply that every control is used exactly once. If there are more controls than treated units, some controls can remain unused. In either case, a feasible solution must exist: every treated unit needs an allowed partner, and the no-reuse restrictions must be jointly satisfiable.

A Numerical Assignment and Its Feasible Solutions

Suppose a hypothetical study has three treated units, \(T_1,T_2,T_3\), and three controls, \(C_1,C_2,C_3\). The design uses a one-to-one ratio, retains all six units, and permits each control to be used once. The entries below are matching costs; “Forbidden” means the pair cannot be selected.

	Control \(C_1\)	Control \(C_2\)	Control \(C_3\)
Treated \(T_1\)	1	4	Forbidden
Treated \(T_2\)	2	1	5
Treated \(T_3\)	Forbidden	3	2

Because each treated unit must receive exactly one control and every control is used once in this equal-sized example, a complete assignment corresponds to a permutation of the three controls. There are \(3!=6\) such permutations before prohibitions are applied. Listing them prevents an attractive but invalid assignment from being mistaken for the optimum.

Worked Example: Enumerating the Feasible Assignments

List the possible one-to-one assignments for the cost table above, discard any assignment containing a forbidden pair, and find the minimum total cost.

Assignment 1: \(T_1\) to \(C_1\), \(T_2\) to \(C_2\), and \(T_3\) to \(C_3\). All three pairs are allowed, and the total is \(1+1+2=4\).

Assignment 2: \(T_1\) to \(C_1\), \(T_2\) to \(C_3\), and \(T_3\) to \(C_2\). All pairs are allowed, and the total is \(1+5+3=9\).

Assignment 3: \(T_1\) to \(C_2\), \(T_2\) to \(C_1\), and \(T_3\) to \(C_3\). All pairs are allowed, and the total is \(4+2+2=8\).

The other three permutations are infeasible. The permutation assigning \(T_3\) to \(C_1\) is forbidden in two of them, and the remaining permutation assigns \(T_1\) to the forbidden pair \((T_1,C_3)\). Thus the feasible totals are 4, 9, and 8. The minimum is 4, so the optimal assignment is \(T_1\!-\!C_1\), \(T_2\!-\!C_2\), and \(T_3\!-\!C_3\).

The reported objective value is the sum of the selected costs, in the units of the chosen cost definition. It is not a treatment-effect estimate. The assignment identifies which units are paired under this design; outcomes have not entered the calculation.

Why the Minimum Is a Global, Constrained Minimum

For a small problem, enumeration proves optimality directly: every feasible assignment is listed, its total cost is calculated, and the smallest total is selected. For a larger problem, an assignment algorithm can solve the same objective and constraints without listing every permutation. The algorithm changes how the minimum is found, not what “optimal” means.

\min_{\{x_{ij}\}} \ \sum_{i\in T}\sum_{j\in C} d_{ij}x_{ij}

The binary variables ensure that each pair is either selected or not selected. The treated-unit equality constraints enforce the fixed one-control-per-treated ratio. The control-unit inequalities prevent reuse. Setting \(x_{ij}=0\) for prohibited pairs ensures that the optimizer cannot use them, even if their numerical costs would otherwise make them attractive.

Justification of the enumeration approach: In a one-to-one assignment with equal numbers of treated and control units, any valid assignment gives each treated unit one distinct control. The selected controls are therefore a permutation of all controls. Conversely, any such permutation that uses no forbidden pair satisfies the constraints. Consequently, comparing the total costs of all allowed permutations examines every feasible solution; the least total is a global minimum.

This argument also shows why a local choice need not solve the global problem. Assigning a control to one treated unit changes which controls remain available for the others. The relevant quantity is the total cost of the complete assignment, not the cost of an isolated pair.

Worked Example: A Greedy Choice Can Miss the Optimum

Consider two treated units and two controls, with every pair allowed and a one-to-one ratio. The hypothetical costs are \(d_{11}=1\), \(d_{12}=2\), \(d_{21}=1.5\), and \(d_{22}=100\). Compare the two complete assignments.

The assignment that gives \(T_1\) its cheapest pair first selects \(T_1\!-\!C_1\), at cost 1. Since \(C_1\) cannot be reused, \(T_2\) must take \(C_2\), giving a total of \(1+100=101\).

The other complete assignment pairs \(T_1\) with \(C_2\) and \(T_2\) with \(C_1\). Its total is \(2+1.5=3.5\), which is much smaller than 101. Therefore the global optimum is \(T_1\!-\!C_2\), \(T_2\!-\!C_1\), despite \(C_2\) not being \(T_1\)’s nearest control.

This example does not imply that a greedy procedure is always poor; it shows that local nearest choices do not, in general, guarantee the minimum total cost under no-reuse constraints. An optimal assignment evaluates the joint allocation.

Making and Checking Forbidden-Pair Decisions

A prohibition should have a clear design meaning. One common rule is a caliper: a pair is allowed only if its distance is no greater than a chosen threshold. For example, if \(d_{ij}\) is the absolute difference in estimated propensity scores and the prespecified caliper is 0.25, then a pair with distance 0.28 is forbidden. A pair with distance 0.22 remains feasible and contributes 0.22 to the objective if that same distance is the matching cost.

Worked Example: Applying a Caliper Before Optimization

Suppose three treated units have hypothetical estimated propensity scores 0.10, 0.30, and 0.50, and three controls have scores 0.12, 0.38, and 0.52. Use absolute propensity-score difference as the cost and impose a caliper of 0.25, so a pair is allowed exactly when its cost is at most 0.25.

For \(T_1\), the distances to \(C_1,C_2,C_3\) are \(|0.10-0.12|=0.02\), \(|0.10-0.38|=0.28\), and \(|0.10-0.52|=0.42\). Thus only \(T_1\!-\!C_1\) is allowed. For \(T_2\), the distances are 0.18, 0.08, and 0.22, so all three pairs are allowed. For \(T_3\), the distances are 0.38, 0.12, and 0.02, so only \(T_3\!-\!C_2\) and \(T_3\!-\!C_3\) are allowed.

Since \(T_1\) must use \(C_1\), the remaining controls for \(T_2\) and \(T_3\) are \(C_2\) and \(C_3\). One feasible assignment is \(T_1\!-\!C_1\), \(T_2\!-\!C_2\), \(T_3\!-\!C_3\), with total cost \(0.02+0.08+0.02=0.12\). The other is \(T_1\!-\!C_1\), \(T_2\!-\!C_3\), \(T_3\!-\!C_2\), with total \(0.02+0.22+0.12=0.36\). Hence the first assignment is optimal among the feasible assignments.

This calculation checks both parts of the design: costs are computed from the stated scores, and pairs above the caliper are excluded rather than merely penalized. The caliper does not guarantee that an assignment exists in every data set; feasibility still needs to be checked.

Diagnostics, Alternatives, and Limits

Before interpreting the output, verify that the optimization problem matches the intended design. A useful audit is to confirm the ratio, unit counts, cost definition, threshold rule, and control-reuse constraint; then check that each selected pair is allowed and that each treated unit has exactly one selected control. Recompute the reported total from the selected entries. For a small example, enumerate all feasible assignments independently as a transparent check.

If the constraints admit no complete assignment, the specified design is infeasible. This may occur because a treated unit has no allowed control, or because several treated units can only be assigned to too few distinct controls. Do not describe an infeasible assignment as the optimum. Revisit the design choices—such as the caliper or the requirement to retain every treated unit—and state any change before solving the revised problem.

The cost function is also a substantive design choice. Minimizing absolute propensity-score differences, for example, need not give the same assignment as minimizing distances on a logit-propensity scale or a multivariable distance. The optimizer can only minimize the costs supplied to it; it cannot decide whether the distance definition is appropriate or whether the chosen threshold is scientifically defensible.

Nearest-neighbor matching makes a local selection according to a rule such as choosing the closest available control. Constrained optimal matching instead minimizes the total cost over complete assignments that satisfy the specified restrictions. A caliper can be added to either approach as a feasibility rule, but it does not turn local choices into a global optimum. Full matching allows matched sets with different numbers of treated and control units, whereas this problem fixes a one-to-one pair structure. These approaches answer different design needs; none is automatically best in all applications.

Finally, optimality is a statement about the defined assignment problem, not a guarantee of causal identification or good covariate balance. Matching on observed variables does not by itself rule out unmeasured confounding. The causal interpretation of a later outcome analysis depends on the study’s identifying assumptions and on whether the resulting matched sample is suitable for the target question. A low total cost is not itself evidence that all relevant covariates are balanced, that the selected units represent a desired population, or that a treatment effect has been estimated.

Common pitfall: “Each treated unit got its closest control, so the matching must have the smallest possible total distance.” This reasoning ignores competition for controls: a control assigned to one treated unit is unavailable to another. The correction is to compare complete feasible assignments—or solve the stated global optimization problem—and to verify that every selected pair obeys the prohibitions.

Check Your Understanding

Answer each question using the definitions and procedures above. Brief solutions follow the questions.

In one-to-one matching, what does the constraint \(\sum_j x_{ij}=1\) require for each treated unit?
A pair has cost 0.31 under a caliper of 0.30. Is it a costly feasible pair or a forbidden pair?
For a two-treated, two-control problem, the two feasible assignment totals are 6.2 and 5.7. Which assignment is optimal, and why?
Why does a minimum total matching cost not establish that a treatment effect is unbiased?
What should be concluded if no complete assignment satisfies the ratio, no-reuse rule, and forbidden-pair constraints?

Solutions. (1) Treated unit \(i\) must be assigned exactly one control. (2) It is forbidden because 0.31 exceeds the 0.30 caliper; it cannot be selected. (3) The assignment with total 5.7 is optimal because it has the lower total among the feasible assignments. (4) The objective concerns the chosen matching costs, not unmeasured confounding or the causal identification assumptions needed for an unbiased effect estimate. (5) The specified design is infeasible; revise a design constraint only with an explicit justification, then solve the revised problem.