Lagrangian relaxation of an assignment with side constraints

Retaining integer assignment equations while dualizing extra capacity inequalities gives an easily evaluated upper bound for a maximization problem. With multipliers $\lambda \ge 0$ and capacities $b$, it is $\theta (\lambda )={\max }_{x\text{ assignment}}[c^{T}x+{\lambda }^T(b-Ax)]$. It is a convex maximum of affine functions. Minimizing it exploits the convex hull of assignments, so it can have a finite optimum when only a fractional mixture satisfies the side constraints and no integer assignment does. This separates a useful relaxation bound from a certificate of integer feasibility.