This lecture explains how to solve discrete optimization problems by relaxing integrality constraints, turning them into linear optimization problems. The relaxation provides a lower bound on the optimal solution, but rounding the relaxed solution may not work for finding feasible solutions.