= Solution
The retained <integer> assignment constraints have only two feasible matrices,
$$
D=\begin{pmatrix}1&0\\0&1\end{pmatrix},\qquad O=\begin{pmatrix}0&1\\1&0\end{pmatrix}.
$$
Their $(a\cdot x,b\cdot x,c\cdot x)$ totals are $(4,5,10)$ and $(3,6,8)$ respectively. For nonnegative <Lagrange multipliers> $\lambda,\mu$, add $\lambda(3.5-a\cdot x)+\mu(5.5-b\cdot x)$ to the maximization objective. Each <feasible point> gains a nonnegative amount, so maximizing over the retained assignment set gives an <upper bound>:
$$
\theta(\lambda,\mu)=\max\left\{10-\frac\lambda2+\frac\mu2,\quad8+\frac\lambda2-\frac\mu2\right\}.
$$
The <Lagrangian dual problem> minimizes this convex piecewise-linear function over $\lambda,\mu\geq0$. Put $d=\lambda-\mu$; every real $d$ can occur. The two affine terms average to nine, so their maximum is at least nine, with equality exactly when $d=2$. Thus
$$
\boxed{\min_{\lambda,\mu\geq0}\theta=9,\qquad(\lambda,\mu)=(2+t,t),\quad t\geq0.}
$$
Neither <integer> assignment satisfies both side constraints: $D$ violates the $a$ bound and $O$ the $b$ bound. The finite dual bound is therefore not evidence that the <integer> primal is feasible. The following part shows why this <Lagrangian relaxation of an assignment with side constraints> has a finite value anyway.
Back to article page
