<p>While trying to understand <a href="https://epubs.siam.org/doi/pdf/10.1137/0603052" rel="nofollow noreferrer">this paper</a> by Hammer, Hansen and Simeone, I came across some terminology I was unfamiliar with: the notion of a &quot;strongly complementary pair&quot;.</p>
<p>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 &quot;strongly complementary&quot; (see below), but I could not find a proper definition for it.</p>
<p>The relevant sentence from the paper is the following one from their proof of Theorem 4.1:</p>
<blockquote>
<p>Consider an optimal solution <span class="math-container">$X$</span> of [the primal] and an optimal solution <span class="math-container">$\lambda$</span>
of [the dual] such that <span class="math-container">$(X, \lambda)$</span> is a strongly complementary pair.</p>
</blockquote>
<p>It is implied that such a pair always exists. Furthermore, in the context of this sentence, it is known that there is some variable <span class="math-container">$x_i$</span> in the primal which takes value <span class="math-container">$0$</span> in all optimal solutions (so in particular also in <span class="math-container">$X$</span>). The conclusion that is then immediately drawn from the fact that <span class="math-container">$X$</span> and <span class="math-container">$\lambda$</span> form a strongly complementary pair is that the inequality in the dual corresponding to variable <span class="math-container">$x_i$</span> from the primal is satisfied with strict inequality.</p>
<p>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 <a href="https://www.jstor.org/stable/pdf/171673.pdf" rel="nofollow noreferrer">this 1965 publication</a> 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 &quot;strongly complementary pairs&quot; at all. Possibly only under a different name, making it hard to find among its 60 pages.</p>
<p>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.</p>

CC BY-SA 4.0
2022-10-29T13:50:13.480Z
(i) The title says "integer program" but your post talks about linear programs.  Which do you want to ask about? (ii) It's a standard result that for an LP any optimal primal solution and optimal dual solution satisfy complimentary slackness.  Is this what you are asking about?
Neal Young
CC BY-SA 4.0
2022-10-29T20:06:34.453Z
Also, it's certainly possible in general for a variable in an optimal primal solution solution to be zero while the corresponding constraint in an optimal dual solution is tight.  (Consider e.g. primal $\min \{z : z\ge 0; z \le 0\}$, which has dual $\max\{y : y \le 0; y \ge 0.\}$) What cannot happen is that the primal variable is non-zero while the dual constraint is not tight..
Neal Young
CC BY-SA 4.0
2022-10-31T09:06:10.567Z
(i) I meant linear programs, thanks. I updated the title accordingly. (ii) That is not exactly what I am asking about. Indeed complementary slackness tells us that for a pair of optimal primal/dual solutions *at least* one of the following holds: (a) a variable in the primal solution is 0; (b) the corresponding constraint in the dual is satisfied with strict inequality. The paper in question however seems to suggest that a pair of optimal primal/dual solutions can be found for which *exactly* one of those holds. I'm wondering when that is true (if my interpretation is correct at all).
RubenVerhaegh
CC BY-SA 4.0
2022-10-31T17:54:55.847Z
I think one can show that there are optimal dual solutions $x$ and $y$ such that, for each dual variable $y_i$ such that $y_i=0$ and the corresponding primal constraint constraint is tight (i.e. the condition you want to avoid holds), then *every optimal dual solution has $y_i=0$, and in every optimal primal solution the corresponding constraint is tight*.  I'm not sure what the significance of the latter property is, though.
Neal Young
<terminology><integer-programming><primal-dual>
What is a "strongly complementary pair" of primal/dual solutions to a linear program?
RubenVerhaegh
# What is a "strongly complementary pair" of primal/dual solutions to a linear program?

(Asked by: username_0 on 2022-10-28)

While trying to understand [this paper](https://epubs.siam.org/doi/pdf/10.1137/0603052) 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](https://www.jstor.org/stable/pdf/171673.pdf) 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.

**Tags:** terminology, integer-programming, primal-dual

> **Comments:**
> **username_1**: (i) The title says "integer program" but your post talks about linear programs.  Which do you want to ask about? (ii) It's a standard result that for an LP any optimal primal solution and optimal dual solution satisfy complimentary slackness.  Is this what you are asking about?  
> **username_1**: Also, it's certainly possible in general for a variable in an optimal primal solution solution to be zero while the corresponding constraint in an optimal dual solution is tight.  (Consider e.g. primal $\min \{z : z\ge 0; z \le 0\}$, which has dual $\max\{y : y \le 0; y \ge 0.\}$) What cannot happen is that the primal variable is non-zero while the dual constraint is not tight..  
> **username_0**: (i) I meant linear programs, thanks. I updated the title accordingly. (ii) That is not exactly what I am asking about. Indeed complementary slackness tells us that for a pair of optimal primal/dual solutions *at least* one of the following holds: (a) a variable in the primal solution is 0; (b) the corresponding constraint in the dual is satisfied with strict inequality. The paper in question however seems to suggest that a pair of optimal primal/dual solutions can be found for which *exactly* one of those holds. I'm wondering when that is true (if my interpretation is correct at all).  
> **username_1**: I think one can show that there are optimal dual solutions $x$ and $y$ such that, for each dual variable $y_i$ such that $y_i=0$ and the corresponding primal constraint constraint is tight (i.e. the condition you want to avoid holds), then *every optimal dual solution has $y_i=0$, and in every optimal primal solution the corresponding constraint is tight*.  I'm not sure what the significance of the latter property is, though.  

---

## 0 answers

