1
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ (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? $\endgroup$
    – Neal Young
    Oct 29, 2022 at 13:50
  • $\begingroup$ 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.. $\endgroup$
    – Neal Young
    Oct 29, 2022 at 20:06
  • $\begingroup$ (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). $\endgroup$
    – RubenVerhaegh
    Oct 31, 2022 at 9:06
  • $\begingroup$ 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. $\endgroup$
    – Neal Young
    Oct 31, 2022 at 17:54

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.