Why Use a Linear Program?
Separation is a geometric property of the observed binary responses and their design rows. A plot can make the property visible when there is one predictor, but that approach is difficult with many predictors, factor contrasts, or interactions. Linear programming translates the geometric question into a finite set of inequalities that a solver can check directly.
The tests in this tutorial use the fixed-effects design matrix. They are useful for diagnosing whether a linear combination of the fixed-effect columns separates the observed outcomes. In a GLMM, that design-level result is a diagnostic, not a complete analysis of the likelihood that integrates over random effects. The tests do not themselves establish that a particular fitting algorithm has converged or characterize every source of instability.
Here \(b\) is a direction in the fixed-effect coefficient space, not an estimate of the model coefficients. The signed-row construction combines the two outcome groups into one set of inequalities. If \(y_i=1\), then \(a_i=x_i\), so a positive signed value means \(x_i b>0\). If \(y_i=0\), then \(a_i=-x_i\), so a positive signed value means \(x_i b<0\). Thus positive signed values point toward the observed class in both groups.
The basic formulation assumes a fixed, finite design matrix, binary outcomes, and a linear predictor \(x_i b\) with no offset. The design can contain continuous predictors, indicator columns, and their interactions. Repeated or identical design rows are retained as separate observations. The inequalities concern the observed rows, not every possible covariate value.
Two Feasibility Problems
A strict inequality is inconvenient for a linear program, but in a finite data set it can be replaced by a margin of one. If every \(a_i b\) is strictly positive, the smallest of these finitely many values is positive. Multiplying \(b\) by the reciprocal of that smallest value makes every signed value at least one. Conversely, if all signed values are at least one, they are strictly positive. This gives an exact feasibility test for complete separation.
A feasible solution proves that the design is completely separated. If the problem is infeasible, there is no direction with strictly positive signed values for every observation. That does not rule out quasi-complete separation: some signed values may be zero while the rest are nonnegative.
For the weak test, require all signed values to be nonnegative and require their sum to be positive. Since the signed values are nonnegative, a positive sum means at least one is strictly positive. As before, a positive sum can be scaled to at least one.
The weak-separation LP includes both complete and quasi-complete separation. The classification therefore uses the two results together: if the complete LP is feasible, the design is completely separated; if it is infeasible but the weak LP is feasible, the design is quasi-completely separated; if both are infeasible, there is no nonzero weak separating direction for these rows. The last case is commonly described as overlap in the design geometry.
| Complete LP | Weak LP | Design-level conclusion |
|---|---|---|
| Feasible | Feasible | Complete separation |
| Infeasible | Feasible | Quasi-complete separation |
| Infeasible | Infeasible | No weak separating direction |
Both programs are linear feasibility problems: their constraints are linear in the entries of \(b\). The coefficients are the entries of the signed design rows. A solver may represent each unrestricted coefficient as the difference of two nonnegative variables; this changes the computational representation, not the test. No objective function is needed for these feasibility formulations.
Worked Examples
Worked Example: Complete Separation by a Continuous Predictor
Suppose a hypothetical binary-response data set has an intercept and one predictor \(x\). Its four observations are \((x,y)=(-2,0),(-1,0),(1,1),(2,1)\). The design row is \(x_i=(1,x)\). Determine whether the complete-separation LP is feasible.
The signed rows \(a_i=(2y_i-1)x_i\) are \((-1,2),(-1,1),(1,1),(1,2)\), in the same order as the observations. Choose \(b=(0,1)\), so the signed values are
Every value is at least one, so \(b=(0,1)\) is a feasible solution to the complete LP. The direction assigns negative linear predictors to the two \(y=0\) observations and positive linear predictors to the two \(y=1\) observations. The design is completely separated. These values demonstrate feasibility; they are not estimates obtained by fitting a logistic mixed model.
Worked Example: Quasi-Complete Separation from a Shared Boundary
Consider a hypothetical design with four observations: \((x,y)=(-1,0),(0,0),(0,1),(1,1)\), again with \(x_i=(1,x)\). The two outcomes at \(x=0\) share the same predictor value. Classify the design using the two LPs.
The signed rows are \((-1,1),(-1,0),(1,0),(1,1)\). Taking \(b=(0,1)\) gives signed values \(1,0,0,1\). They are all nonnegative and sum to \(2\). Scaling \(b\) by \(1/2\) makes the sum equal to one, so the weak LP is feasible.
The complete LP cannot be feasible: the constraints from the two observations at \(x=0\) would require both \(-b_0\ge 1\) and \(b_0\ge 1\), where \(b_0\) is the intercept component. Adding these inequalities gives \(0\ge 2\), a contradiction. Thus complete separation is impossible, while a weak separating direction exists. The design is quasi-completely separated. Geometrically, the two boundary observations must have signed value zero, while the observations away from the boundary can have strictly positive signed values.
Worked Example: Neither Complete nor Quasi-Complete Separation
Now suppose a hypothetical design has \((x,y)=(0,0),(0,1),(1,0),(1,1)\), with design rows \(x_i=(1,x)\). Check whether there is any weak separating direction.
At \(x=0\), the signed rows are \((-1,0)\) and \((1,0)\). The weak inequalities for these rows require \(-b_0\ge 0\) and \(b_0\ge 0\), so \(b_0=0\). At \(x=1\), the signed rows are \((-1,-1)\) and \((1,1)\). Their weak inequalities require \(-(b_0+b_1)\ge 0\) and \(b_0+b_1\ge 0\), so \(b_0+b_1=0\). Together these equations imply \(b_0=b_1=0\).
For this only possible weak direction, the sum of signed values is zero, not at least one. Therefore the weak LP is infeasible; the complete LP is infeasible as well. The design has neither complete nor quasi-complete separation. At each predictor value both outcomes occur, so the signed inequalities force every candidate direction to vanish on the observed design.
Justification and Practical Interpretation
The equivalence between the LPs and the geometric definitions follows from two simple scaling arguments. For complete separation, strict positivity over finitely many observations gives a positive minimum margin. For weak separation, nonnegative margins with at least one positive value give a positive sum. In either case, multiplying the direction by a positive constant preserves the signs and can meet the LP's unit threshold.
For each observation, compute \(a_i=(2y_i-1)x_i\). Check that the outcome coding is exactly 0 and 1 and that the rows contain the fixed-effect columns being assessed.
Ask whether one vector \(b\) satisfies \(a_i b\ge 1\) for every observation. A feasible solution establishes complete separation.
If the complete LP is infeasible, check whether all margins can be nonnegative while their sum is at least one. Feasibility establishes quasi-complete separation in this case.
Substitute the solver's candidate \(b\) into the signed margins, inspect their signs, and report which observations have zero margins. If neither LP is feasible, report that no weak separating direction was found for the stated design.
An LP solver typically returns either a feasible vector or an infeasibility result. A candidate vector should be checked by recomputing every \(a_i b\) from the original design. In finite-precision computation, values near zero or near the feasibility tolerance need special attention: rounding can make a small positive margin appear to be zero, or a small negative margin appear nonnegative. Rescaling predictors and using sensible solver tolerances can help, but the data coding and final margins should still be inspected.
The test depends on the design matrix as specified. Changing factor contrasts, dropping a column, or omitting an interaction changes the coefficient coordinates and can change the model being diagnosed. An invertible reparameterization of the same column space does not change whether a separating direction exists, but changing the column space can. The test also does not account for an offset; an offset introduces fixed terms into the inequalities and requires a formulation suited to that model.
What the Test Does—and Does Not—Say
A useful alternative is geometric inspection. A scatterplot may reveal a separating line or boundary in a one- or two-predictor problem and can help explain the LP result. However, plots become ambiguous in higher dimensions, and visual inspection can miss boundary observations that turn complete separation into quasi-complete separation. The LP provides a systematic test of the specified finite design.
Another practical signal is difficulty fitting a binary-response model, such as very large coefficients or unstable optimization. Such output may prompt a separation check, but it is not itself a test: optimization problems can have other causes, and a feasibility result does not diagnose all convergence failures. The LP is most informative when treated as a targeted geometric diagnostic alongside careful checks of model specification and fitting output.
For a GLMM, the scope distinction matters. These programs use \(x_i b\), the fixed-effects design contribution. They do not include random-effect realizations, variance parameters, or integration over the random-effects distribution. A feasible fixed-effects separator is therefore evidence of separation geometry in that design component, not a standalone proof of every consequence for a particular mixed-model likelihood. Conversely, an infeasible result does not rule out every possible numerical or inferential difficulty in fitting the GLMM.
The main value of the LP formulation is that it makes the distinction explicit. The complete test asks whether every observed row can have a strictly correct sign; the weak test asks whether all signs can be correct or tied, with at least one strict sign. Keeping the tests separate prevents boundary observations from being overlooked and makes the conclusion reproducible from the design matrix.
Check Your Understanding
Answer each question, then compare your reasoning with the solutions.
- For an observation with \(y_i=0\) and \(x_i=(1,3)\), what is its signed row \(a_i\)?
- Why can a complete-separation condition with strict inequalities be replaced by constraints \(a_i b\ge 1\) on a finite data set?
- A complete LP is infeasible, but the weak LP is feasible. What is the design-level classification?
- In the quasi-complete example, why do the two observations at \(x=0\) prevent complete separation?
- What does a fixed-effects LP result establish, and what does it not establish about a GLMM fit?
Solutions. (1) Since \(2y_i-1=-1\), \(a_i=-(1,3)=(-1,-3)\). (2) If every one of finitely many margins is positive, their minimum is positive; rescaling \(b\) by the reciprocal of that minimum makes every margin at least one. (3) Quasi-complete separation. (4) The two outcomes have the same design row, so their strict signed inequalities require both \(b_0\ge 1\) and \(-b_0\ge 1\), which cannot both hold. (5) It establishes whether the stated fixed-effects design has a complete or weak separating direction; by itself it does not solve the integrated GLMM likelihood or diagnose every cause of fitting difficulty.