While trying to understand this paper by Hammer, Hansen and Simeone, I came across some terminology I was unfamiliar with: the notion of a "strongly complementary pair".
For a linear program and its dual, a strongly complementary pair refers to a pair of two solutions: one for the primal and one for the dual, with some relation between them that is not specified in the paper. From the conclusions drawn from this pair, I can deduce to some extent what this relation is that makes them "strongly complementary" (see below), but I could not find a proper definition for it.
The relevant sentence from the paper is the following one from their proof of Theorem 4.1:
Consider an optimal solution $X$ of [the primal] and an optimal solution $\lambda$ of [the dual] such that $(X, \lambda)$ is a strongly complementary pair.
It is implied that such a pair always exists. Furthermore, in the context of this sentence, it is known that there is some variable $x_i$ in the primal which takes value $0$ in all optimal solutions (so in particular also in $X$). The conclusion that is then immediately drawn from the fact that $X$ and $\lambda$ form a strongly complementary pair is that the inequality in the dual corresponding to variable $x_i$ from the primal is satisfied with strict inequality.
I see the relationship with complementary slackness, but it also appears that the existence of a strongly complementary pair (which is possibly always (?)) suggests some stronger result than just that. Most papers I could find that also mention such pairs were from the same authors. These often referred back to this 1965 publication and state that this paper provides an algorithm to find such pairs. After thoroughly ctrl+f -ing said publication however, it does not appear to mention "strongly complementary pairs" at all. Possibly only under a different name, making it hard to find among its 60 pages.
My question is therefore, what is a strongly complementary pair in this context? And additionally (which might follow directly from a definition), does such a pair exist for every linear program? Because if that is the case, I would be interested in reading the proof for it.