= Lagrangian relaxation of an assignment with side constraints
{c}
Retaining <integer> assignment equations while dualizing extra capacity inequalities gives an easily evaluated <upper bound> for a maximization problem. With multipliers $\lambda\geq0$ and capacities $b$, it is $\theta(\lambda)=\max_{x\text{ assignment}}[c^Tx+\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.
Back to article page
