Duality pairs every optimization problem (primal) with a dual that provides bounds. Weak duality states the dual optimal ≤ primal optimal for minimization problems — always. Strong duality holds (gap = 0) when Slater's condition is satisfied for convex programs, or when the LP has a feasible interior. The duality gap measures how far apart primal and dual solutions are — a nonzero gap indicates either non-convexity or constraint qualification failure. In integer programming, the duality gap is always non-negative and is the key challenge: SDP relaxations and Lagrangian relaxation provide the tightest convex bounds.