---
slug: continuous_relaxation
name: Continuous Relaxation
one_liner: "Make a hard discrete/combinatorial problem tractable by embedding its integer feasible set into a continuous superset, solving the easier (often convex) relaxed surrogate, then rounding the continuous optimum back to feasibility — with the relaxation gap bounding the true discrete optimum."
type: prime
schema_version: 2
status: density_v2_draft
categories: [structural, computational, mathematical]
origin_domain: combinatorial_optimization
alternate_origin_domains: [operations_research, machine_learning, theoretical_computer_science, economics]
aliases: [lp_relaxation, convex_relaxation, relax_and_round, integrality_gap, semidefinite_relaxation, discrete_to_continuous_embedding]
related: []
solution_archetypes: []
review_flags:
- "OPERATOR-DERIVED (op-04 spatialization/scaling, flavor 4b / discrete→continuous) — the STRUCTURE obtained by relaxing the integrality constraint of a hard discrete/combinatorial problem so its variables may take continuous values, yielding an easier (often convex) surrogate that bounds and guides the discrete solution. Derived from `graph_coloring` and `greedy_algorithm`. Discovered 2026-07-03. STRONG hold (verified absent from corpus; established named technique — LP/convex/semidefinite relaxation in OR and combinatorial optimization). CONVERGENCE ×2. STATUS: HOLD pending owner keep/cut."
- "Created 2026-07-03; STUB ONLY (frontmatter + Core Idea + Notes). SI/SF/similarity are PROPOSER ESTIMATES pending triangulation. Body sections (Structural Signature onward) NOT written."
- "Phase-C action: re-similarity-check vs `optimization` (nearest, present), `approximation`, `discreteness`/`continuity`, `convexity` (if present), and any bound/surrogate prime; confirm the embed-relax-bound-round anatomy is a distinct reusable strategy and not merely a technique-instance of `optimization`/`approximation`; draw a subsumption/relation edge `optimization` → `continuous_relaxation` and add a boundary note vs `approximation` at incorporation; write a v1 draft and sync the one_liner across v1/v2 per CLAUDE.md before merge."
substrate_independence:
  composite_substrate_independence: 4
  domain_breadth: 5
  structural_abstraction: 4
  transfer_evidence: 4
  reasoning: 'The bare structure — embed a discrete feasible set into a continuous superset, solve the (often convex) relaxed surrogate, use the relaxed optimum as a bound on the true discrete optimum, then round/project back to feasibility — is genuinely substrate-neutral. It recurs across structurally-unlike domains: LP/SDP relaxation of integer programs and scheduling/assignment in operations research, relaxation of discrete latent variables (Gumbel-softmax, the concrete distribution) in machine learning, approximation algorithms built on LP/SDP relaxations in theoretical CS, and the relaxing of indivisibilities in economics. These siblings share only the abstract embed-relax-bound-round engine, so domain_breadth scores 5. Structural abstraction is 4 because the core is a pure statement about a feasible-set embedding and a bound relationship (the "integrality gap") that requires no particular substance to hold; it stays just short of 5 because the framing leans on optimization vocabulary (feasible set, optimum, rounding), a mild domain residue. Transfer evidence is strong — the strategy is independently named and heavily used in OR, ML, and TCS.'
similarity_to_nearest_existing_prime:
  slug: optimization
  similarity: 0.6
structural_framed:
  label: structural
  aggregate: 0.4
  criteria: {vocab_travels: 0.7, evaluative_weight: 0.3, institutional_origin: 0.1, human_practice_bound: 0.3, import_vs_recognize: 0.5}
  rationale: 'Reads structural-to-mixed. The core claim — a hard discrete problem is made tractable by embedding its feasible set into a continuous superset, solving a convex surrogate, and rounding back under a bound relationship — is recognized rather than imported, and travels cleanly into integer programming, relaxed discrete latent variables in ML, and LP/SDP approximation algorithms without carrying any single domain''s substance. The frame residue is light but present: "feasible set," "optimum," "rounding," and "integrality gap" import optimization/mathematical vocabulary (keeping import_vs_recognize and human_practice_bound off the floor), but the underlying structure — discrete embedding + solvable surrogate + gap bound + projection to feasibility — is substrate-neutral. Somewhat lower framing than the framed-stratum candidates; comparable to its parent `optimization`.'
phase_b_passes_completed: []
---
# Continuous Relaxation

## Core Idea

Continuous relaxation takes a hard *discrete* or *combinatorial* problem — one whose variables must be integers, or 0/1, or a permutation — and *relaxes the integrality constraint* so those variables may instead take continuous values. This produces an easier continuous problem (frequently convex, and therefore solvable by gradients or by polynomial-time convex methods) whose solution then bounds and guides the discrete one. The feature present in the relaxed form but absent at the discrete level is precisely *smoothness*: at the discrete level the feasible set is a finite lattice of isolated points with no gradient to descend and, in the worst case, no route to the optimum short of combinatorial search; embed that lattice into a continuous superset and the problem acquires a landscape — directions, slopes, and (when convex) a single basin — that can be navigated efficiently.

The load-bearing anatomy is a four-part structure the discrete problem does not name: (1) an *embedding* of the discrete feasible set into a continuous superset (the integer points become the corners, or a subset, of a continuous body); (2) a *solvable surrogate* — often a convex program — defined on that superset; (3) a *bound relationship* between the relaxed optimum and the true discrete optimum, the "integrality gap," which certifies how far the easy answer can be from the hard one; and (4) a *rounding or projection* that maps the continuous solution back to a feasible discrete point. The relaxation is not the answer — it is a scaffold: the continuous optimum lower-bounds (or upper-bounds) the discrete one, telling you both a target and a certificate, and the rounding step converts guidance into a feasible discrete solution whose sub-optimality is controlled by the gap. This embed-relax-bound-round loop is a *general problem-solving strategy*, not a fact about any one problem.

Read structurally, the same shape appears wherever a hard discrete problem is attacked by continuous embedding, and the siblings are genuinely unlike. In *operations research and integer programming*, LP relaxation drops the integrality of a 0/1 or integer program, solves the linear surrogate, and rounds or branches — the workhorse of scheduling, assignment, and routing. In *machine learning*, relaxing discrete latent variables (the Gumbel-softmax / concrete distribution) replaces a hard categorical choice with a continuous, differentiable surrogate so that gradients can flow through what was a non-differentiable discrete sample. In *theoretical computer science*, approximation algorithms are built by relaxing a combinatorial problem to an LP or semidefinite program, solving it, and rounding — the integrality gap directly bounds the approximation ratio. In *economics*, relaxing indivisibilities (treating a discrete good as continuously divisible) restores convexity and the existence of prices or equilibria. Across these, the shared abstract engine is: a discrete feasible set embedded in a continuous superset, a solvable surrogate, a gap bound, and a round-back — the combinatorial case is one species; the structurally-unlike siblings show the genus is the bare embed-relax-bound-round structure.

## Notes

**Provenance.** Produced by operator 04 (spatialization / scaling), flavor 4b (discrete → continuous), as the structure absent at the discrete level of `graph_coloring` and `greedy_algorithm` — relax the integrality/combinatorial constraint into a continuous, often convex, surrogate that bounds and guides the discrete solution. Surfaced in the op-04 sweep on 2026-07-03 with cross-input convergence ×2. Established, canonically named technique: continuous relaxation / LP relaxation / convex relaxation in operations research and combinatorial optimization, the relax-and-round paradigm, semidefinite (SDP) relaxation, and — in ML — the Gumbel-softmax / concrete distribution for relaxing discrete latent variables. Claimed siblings: LP/SDP relaxation in OR and approximation algorithms, relaxed discrete latents in ML, and relaxed indivisibilities in economics. Verified absent from the corpus. Manifest: STRONG hold.

**For owner evaluation (keep/cut).** The case FOR is strong: continuous relaxation is a *canonical, named technique* (LP/convex/semidefinite relaxation — not a proposer coinage), verified absent, with a clean and distinctive anatomy — embedding + solvable surrogate + integrality-gap bound + rounding back — and genuinely unlike siblings spanning OR, ML, TCS, and economics. It fills a real gap: a prime for "make a hard discrete problem tractable by continuous embedding, then round" that the corpus's generic `optimization` and `approximation` do not name. The RISKS Kurt should weigh: (1) **is it a distinct prime, or a technique-instance of `optimization`/`approximation`?** — the discriminating claim is that the *embed-relax-bound-round* structure is a general reusable pattern that recurs across OR, ML, and TCS independently of any particular objective; `optimization` names the goal (find a best point) and `approximation` names the tolerance (accept a near-best answer), but neither names the *discrete→continuous embedding plus integrality-gap bound plus round-back* machinery, which is the load-bearing content here. (2) **Overlap with `approximation`** — the two are close but separable: approximation is the *acceptance of an inexact answer*; continuous relaxation is a specific *method for producing one with a certified bound* (the gap). Recommend a boundary note rather than a merge. Sharp keep/cut question: *is "relax the integrality constraint, solve the continuous surrogate, round back" a distinct prime, or is it just `optimization` applied to a discrete problem?* — the proposer's answer is that the continuous embedding and the gap-certified round-back are structure the bare `optimization` prime lacks.

**At incorporation.** Re-run similarity against `optimization` (nearest, present — a general strategy *for* hard optimization, not optimization itself), `approximation`, `discreteness` / `continuity` (the axis the operator moves along), `convexity` (if present in the corpus — the surrogate's typical form), and any bound/surrogate prime. If kept: draw a relation/subsumption edge `optimization` → `continuous_relaxation`, and add a missing-edge note distinguishing it from `approximation` (method-with-certified-bound vs. acceptance-of-inexactness) and connecting it to the discrete/continuous axis and to `convexity` where the surrogate is convex. Write a v1 draft and sync the one_liner across v1 and v2 per CLAUDE.md before merge.
