Exact Continuous Relaxations for Combinatorial Optimization

45 concepts37 papers2 proposals

Combinatorial optimization problems—such as graph matching, clustering, and community detection—are notoriously difficult because of their discrete nature. Traditionally, researchers solve them by "relaxing" the discrete constraints (like $x \in \{0, 1\}$) to continuous ones ($x \in [0, 1]$). However, standard relaxations, such as spectral clustering or simple linear programming relaxations, suffer from an integrality gap: the optimal continuous solution is often fractional (e.g., $x = 0.5$), requiring heuristic rounding steps that destroy theoretical guarantees and introduce approximation errors.

A powerful alternative paradigm has emerged: exact or tight continuous relaxations. Instead of settling for a loose approximation, this approach designs continuous objective functions whose optima are mathematically guaranteed to align perfectly with the solutions of the original discrete problem. By eliminating the integrality gap entirely, we can use fast, gradient-based continuous solvers to find exact discrete solutions.

Forcing Integrality via Concavity and Regularization

How can a continuous optimization landscape guarantee a discrete, binary solution? The core intuition lies in reshaping the landscape so that the optimal points are pushed away from the interior and directly onto the boundaries—the vertices of the continuous feasible region.

One common mechanism is the introduction of concave penalties or regularizers. In a convex minimization problem, the minimum can lie strictly inside the feasible region. However, if we minimize a concave function over a bounded convex set, the minimum is guaranteed to occur at the extreme points (the vertices).

Convex Minimization (Interior Solution)      Concave Minimization (Vertex Solution)
          \     /                                      /           \
           \___/  <- Minimum inside                   /             \
     [---.-------.---]                         *---.-------.-------.* <- Minima at boundaries

For instance, Bo Jiang 0010 et al. utilize an $L_p$-norm regularization framework ($0 < p < 1$) to solve NP-hard optimization problems over permutation matrices, proving that a sufficiently large regularization parameter forces the continuous optimum to be identical to the discrete solution. Similarly, Sara Venturini et al. apply concave penalty functions to mixed-binary hyperparameter optimization, guaranteeing that the continuous relaxation recovers exact binary masks once the penalty exceeds a specific threshold.

This geometric forcing can also be achieved through quadratic regularization and asymptotic control parameters. Marcello Pelillo demonstrates that mapping discrete graph problems to a regularized quadratic objective function ensures that local maxima correspond strictly to maximal cliques, preventing the optimization from getting trapped in non-clique fractional solutions. In graph matching, Haggai Maron et al. show that using Euclidean or geodesic distances naturally forms conditionally concave energy functions when relaxed, causing local optimization algorithms to converge directly to valid discrete permutations without any post-processing. To bridge the gap asymptotically, Tianshu Yu et al. introduce a control parameter that transforms the continuous objective into a quasi-delta function; as this parameter approaches zero, the continuous landscape converges exactly to the discrete solution space.

Total Variation and Geometric Indicator Functions

Another elegant way to achieve exact equivalence is through Total Variation (TV) formulations, particularly in graph partitioning and community detection.

When dividing a graph into clusters, the discrete objective typically counts the number of cut edges while balancing cluster sizes. Arthur Szlam et al. proved that the NP-hard Cheeger cut problem can be perfectly translated into a continuous relaxation using Total Variation. Crucially, the continuous minimizer of this TV functional is not a fuzzy, fractional vector; it behaves as a sharp step function, serving as an exact indicator function that perfectly reveals the optimal discrete cut.

This framework has been extended widely to network modularity optimization. Andrea Cristofari et al. show that discrete combinatorial problems in network modularity can be exactly mapped to a continuous total variation formulation within specific box constraints, ensuring the continuous global maximum corresponds precisely to the optimal discrete community structure. As Huiyi Hu et al. demonstrate, this reformulates discrete network community detection as a continuous energy minimization problem—combining a TV term to penalize edge cuts and an $L_2$ balance term to maintain community size—allowing researchers to apply powerful continuous calculus and differential equation schemes (like the Merriman-Bence-Osher scheme) directly to discrete graphs.

Eliminating the Integrality Gap Across Domains

The primary benefit of a tight relaxation is the complete elimination of the approximation errors that plague traditional methods. As Thomas Bühler et al. explain, a tight continuous relaxation ensures that the minimum value of the continuous objective function matches the minimum value of the original discrete set optimization problem exactly. To generalize this, Matthias Hein et al. introduced a general tightness theorem for balanced graph cuts (such as Ratio Cuts and Normalized Cuts), proving that continuous solvers can directly optimize discrete objectives without an inherent approximation gap.

This exact alignment extends across several distinct optimization domains:

  • Correlation and Partitioning Clustering: Erik Thiel et al. develop a non-convex continuous relaxation for correlation clustering that is mathematically tight, bypassing the large integrality gaps typical of linear or semi-definite programming (SDP) relaxations. For standard partitioning, Martin Ryner et al. show that the continuous relaxation of the clustering assignment problem is naturally tight, meaning the continuous optimal solution is inherently a valid discrete assignment.
  • Hierarchical Clustering: Instead of partitioning data into flat groups, hierarchical clustering builds a tree. Daniel Zügner et al. prove that certain continuous relaxations of hierarchical clustering objectives are integral, meaning their global optima are guaranteed to be valid discrete trees. In a similar vein, Ines Chami et al. demonstrate that continuous relaxations of discrete hierarchical objectives can theoretically and practically achieve near-optimal approximations of the best possible tree structure.
  • Submodular Optimization and Structural Constraints: The correspondence isn't limited to global optima. Marwa El Halabi et al. establish a rigorous theoretical correspondence between critical points in a continuous relaxation and local or strong local minima in the original discrete domain for difference-of-submodular minimization. When structural balance is required, Zhihui Li et al. establish a formal mathematical link between the minimization of specific continuous matrix norms (such as the Exclusive Lasso) and the achievement of perfectly uniform, discrete cluster sizes.

Structural and Algebraic Conditions for Tightness

When exactly does a continuous relaxation become tight? The literature identifies specific algebraic and structural properties of the underlying problem data that guarantee this equivalence.

One classic mechanism is diagonal dominance or diagonal loading. Timothée Cour et al. demonstrate that discrete integer quadratic programs and their continuous relaxations share identical global optima when the underlying weight matrix exhibits diagonal dominance. More recently, Qiheng Lu et al. generalized the classic Motzkin-Straus theorem by showing that a "diagonal loading" technique makes the continuous relaxation of the densest $k$-subgraph problem mathematically tight, ensuring the continuous quadratic program yields the exact discrete subgraph solution when the target size is bounded by the graph's maximum clique.

Other structural properties that guarantee exact continuous-discrete alignment include:

  • Matrix Entry Restrictions: Nicolas Gillis et al. show that for input matrices with entries restricted to $\{-1, +1\}$, the optimal continuous $\ell_1$-norm low-rank matrix approximation is equivalent to a discrete solution, mapping robust matrix factorization directly onto discrete combinatorial problems like MAX CUT.
  • Advanced Matrix Cones: Junyu Zhang et al. demonstrate that completely positive matrix relaxations offer a tighter approximation for modularity maximization than standard semidefinite programming, leading to continuous solutions that more closely reflect true discrete community structures.
  • Continuous Parameter Mapping: Aritra Konar et al. reveal a functional equivalence between optimizing a continuous density-weighting parameter and solving discrete size-constrained subgraph problems, allowing a continuous parameter sweep to map out an entire discrete optimal frontier.
  • Discretization Richness and Solution Basins: Jonas Geiping et al. prove that a discrete optimization solution remains identical to the continuous global optimum if the underlying graph discretization is rich enough to encompass the true boundaries of that optimum. Furthermore, as Ye XUE notes, the existence of wide solution basins in the continuous landscape means that finding any point within a specific continuous region is sufficient to recover an optimal discrete result, drastically reducing the numerical precision required during optimization.

Finally, this theoretical alignment allows for massive computational savings. Ping-Fan Zhao et al. show that sparse quadratic programming relaxations remain theoretically tight under the same conditions as more complex semidefinite relaxations. This allows practitioners to shift from computationally heavy, matrix-based relaxations to lean, vector-based continuous formulations—solving NP-hard discrete problems with the speed of continuous optimization while maintaining absolute mathematical fidelity.

Key Foundational Work

Total Variation Minimization and a Class of Binary MRF Models (2005) — contributed 1 concept elements to this direction.
Replicator Equations, Maximal Cliques, and Graph Isomorphism (1998) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_tight_continuous_relaxation_daa8f46c,
  title = {tight continuous relaxation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/tight-continuous-relaxation/rdr_daa8f46ce75c468e9c1f6ef32749079c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_tight_continuous_relaxation_daa8f46c_v1,
  title = {tight continuous relaxation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/tight-continuous-relaxation/rdr_daa8f46ce75c468e9c1f6ef32749079c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake