Given the boolean LP:

$$\text{Minimize}\;\; c^Tx$$ $$\text{Subject to}\;\; Ax \leq b$$ $$\hspace{57mm} x_i(1-x_i)=0\;\; i=1,...,n$$

Show that the LP relaxation:

$$\text{Minimize}\;\; c^Tx$$ $$\text{Subject to}\;\; Ax \leq b$$ $$\hspace{51mm} 0\leq x_i\leq1\;\; i=1,...,n$$

and the Lagrange relaxation:

$$\text{Maximize}\;\; g(\lambda,v)=\inf_x\Big(c^Tx + \lambda^T(Ax-b) + \sum_{i=1}^nv_ix_i(1-x_i)\Big)$$ $$\text{Subject to}\;\; \lambda \geq 0$$

give equivalent lower bounds on the boolean LP.

My method is to first rewrite the LP relaxation's second constraint as $-x_i(1-x_i)\leq0$, and then to show that its dual can be written as:

$$\text{Maximize}\;\; g(\lambda,v)=\inf_x\Big(c^Tx + \lambda^T(Ax-b) + \sum_{i=1}^nv_ix_i(1-x_i)\Big)$$ $$\text{Subject to}\;\;\lambda\geq0, v \leq 0$$

Since the Lagrange relaxation and the dual of the LP relaxation maximize the same function, with the only difference being the latter has a smaller domain, we can immediately conclude that the Lagrange relaxation is greater than or equal to the dual of the LP relaxation.

What I would like to do is show that they are equal, and then use Slater's condition on the LP relaxation and its associated dual to show strong duality holds, thus proving that both relaxations give identical lower bounds. However I have not been able to prove that they are equal.

I tried finding the value of $x$ as a function of $(\lambda, v)$, but seemed to be getting a resulting function $g(\lambda, v)$ which wasn't concave, which doesn't make sense, can someone help me out with this?

  • $\begingroup$ Seems to me it would just be easier to look at the standard dual of the LP relaxation, and show that it is equivalent to the Lagrange relaxation of the Boolean LP. That is, show that the solution to one dual immediately leads to the solution of the other, and vice versa. $\endgroup$ – Michael Grant Jan 21 '15 at 14:49

$g(x, \lambda, v)$ as a function of $x$ is convex only if $v\leq 0$ (the hessian is diagonal positive semidefinite), otherwise it has at least one negative eigenvalue. Hence for $v\nleqslant0$, $\inf_{x}g(x,\lambda,v)=-\infty$, and thus the max of $g(\lambda, v)$ must be at a point where $v\leq0$.

Therefore the Lagrange relaxation and the dual of the LP relaxation give equivalent lower bounds, and since by Slater's condition the dual of the LP relaxation exhibits strong duality, we can conclude that both relaxations give the same lower bound.

  • $\begingroup$ Just noting that in this case, the hessian is $\text{diag}(v)$ so that the constraint $v \le 0$ might be easier seen by inspection: fixing $\lambda \ge 0$, $g(x) = c + \sum -v_i x_i^2 + b_i x_i$ $\endgroup$ – Mark Sep 14 '18 at 20:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.