Past exam of the integer programming course of the University of Oxford / 2010 / 3

The retained integer assignment constraints have only two feasible matrices,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:The Lagrangian dual problem minimizes this convex piecewise-linear function over $\lambda ,\mu \ge 0$. 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$. ThusNeither 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.

The assignment equalities parameterize every feasible matrix of the linear programming relaxation asThe side totals and objective becomeThe first side constraint gives $t\le 1/2$ and the second gives $t\ge 1/2$, so the relaxation has the unique feasible pointDirect elimination of the assignment equalities has solved this one-dimensional linear program. Its value matches the Lagrangian dual problem value because the retained assignment polytope is the convex hull of the two integer assignments; it does not make the side-constrained integer problem feasible.

With the new right sides, the dual function isTake $\lambda =\mu =t\to \infty$. Then ${\theta }_{\mathrm{new}}(t,t)=10-t\to -\infty$, so the minimization dual is unbounded below:By weak duality, any feasible integer point with finite objective would have to have objective at most every dual value, which is impossible. Thus the modified integer program is infeasible and has no optimal solution. This is an infeasibility certificate from an unbounded Lagrangian dual.

There is also a direct certificate: the assignment equalities force $(a+b)\cdot x=9$, while the new bounds force it to be at most $3+5=8$. Even the modified linear relaxation is infeasible. The earlier $3.5,5.5$ problem also had no integer solution, but there its fractional feasible point kept the dual value finite.