Discrete → continuous (LP / SDP relaxation)

Parent: relaxation

Soften the domain: replace discrete variables x ∈ {0,1} with continuous x ∈ [0,1], solve the (easy, convex) continuous problem, then round back to a discrete answer. The combinatorial hardness melts into a smooth problem where calculus and duality work.

The recipe

1. Relax. An integer program (choosing 0/1) is NP-hard; drop the integrality constraint → a linear program over [0,1], solvable in polynomial time.
2. Solve the continuous relaxation (convex → a global optimum, with KKT/duality certificates).
3. Round the fractional solution back to integers, trying not to lose too much.

The LP optimum is a bound on the true integer optimum (it can only be better), so it also certifies how good your rounded solution is.

SDP and a real theorem

Relax further to semidefinite variables (vectors instead of 0/1): Goemans–Williamson MaxCut relaxes the cut to unit vectors, solves an SDP, then rounds by a random hyperplane — provably within 0.878 of optimal. A logical/combinatorial problem (partition the graph) solved by continuous optimization.

Integrality gap — the price

The continuous optimum can be strictly better than the best discrete one; the ratio is the integrality gap, and it measures exactly what rounding must give up. That's the no-free-lunch tax for buying convexity.

Why it bridges

Discrete satisfiability/feasibility (a logic-flavored search over {0,1}ⁿ) becomes continuous convex optimization, where gradients, Lagrangian duality, and interior-point methods all apply. Relax → solve → round is the standard road from a combinatorial problem into optimization.