Combinatorial optimization problems are ubiquitous across computer science and engineering. Whether scheduling satellite beams, selecting features for a machine learning model, routing power grids, or choosing hyperparameters, we frequently encounter decisions that are fundamentally discrete: a switch is either on or off, a resource is either allocated or not, a network link is either active or inactive.
However, discrete spaces are inherently hostile to modern optimization techniques. They lack derivatives, meaning we cannot calculate a gradient to tell us which direction makes a solution "slightly better." Instead, classical approaches must resort to combinatorial search trees, which suffer from exponential complexity ($2^N$) as the number of variables grows.
Continuous relaxation bypasses this bottleneck. The core intuition is simple: instead of jumping across a jagged, discrete grid of isolated points, we fill the gaps to create a smooth, continuous landscape. This allows optimization algorithms to glide efficiently across the space using gradients or convex optimization tools, before gently guiding the final solution back onto a valid discrete point.
Mapping the Discrete to the Continuous
The first step in continuous relaxation is defining a continuous space that encapsulates the original discrete choices.
Interval and Box Relaxations
The most straightforward mapping replaces a binary choice $x \in \{0, 1\}$ with a continuous interval $x \in [0, 1]$. In this relaxed space, a value of $0.5$ represents maximum uncertainty or a fractional allocation.
For example, in wireless networking, Ye relaxes binary base-station user assignments into fractional values to convert a combinatorial problem into an efficiently solvable convex task. Similarly, Qi et al. transform discrete satellite scheduling decisions into continuous variables between zero and one to enable gradient-based beamforming optimization, while Rao et al. relax on-off sensor activations to navigate a fixed sensing budget.
Geometric Manifolds and Intersections
When constraints are more complex than independent binary choices, researchers map discrete states to sophisticated geometric structures:
- Permutations: A discrete permutation matrix cannot be easily relaxed into independent intervals because its rows and columns must sum to one. To solve this, Linderman et al. relax the discrete space of permutation matrices into the Birkhoff polytope—a continuous space of doubly-stochastic matrices. This smooth manifold allows the use of reparameterization gradients for variational inference.
- Sphere-Box Intersections: To handle exact cardinality constraints (such as selecting exactly $k$ features), Fan et al. and Bibi et al. represent the discrete set $\{0, 1\}$ geometrically as the intersection of a continuous box constraint and a shifted $\ell_2$-sphere. This mapping allows iterative continuous solvers to handle traditionally NP-hard selection tasks.
The Hardening Problem: Penalties and Annealing
If you simply relax a problem and run a standard solver, the optimal continuous solution will often sit squarely in the middle of the relaxed domain (e.g., $x = 0.5$). However, a physical system cannot utilize a fractional solution; a satellite beam cannot be "half-on." We need a mechanism to force the continuous variables back to the discrete boundaries—a process often called "hardening."
Penalty Functions
One dominant strategy introduces an explicit penalty term to the objective function that discourages fractional values. The penalty is designed to be minimized only when variables land precisely on discrete boundaries.
Discrete Space: [0]---------------------------------[1] (No path between)
Relaxed Space: [0]===============(0.5)=============[1] (Smooth path)
With Penalty: [0]\_______________/ \_____________/[1] (Pushed to edges)
Tam et al. and Zhang et al. apply concave penalty functions during iterative linearization to drive fractional network allocations toward binary values. To ensure that hardware constraints are strictly met, Liu utilizes a negative $\ell_2$-norm penalty term, proving that this continuous formulation can achieve global equivalence to the original discrete optimization problem.
Annealing Schedules and Graduated Optimization
Rather than applying a static penalty, another approach dynamically alters the optimization landscape over time. At the beginning of the optimization, the landscape is smoothed out to allow wide exploration. As the algorithm progresses, a control parameter gradually "hardens" the landscape, forcing the variables toward discrete states.
Yamamura et al. formalize this mechanism as "geometric landscape annealing," demonstrating how soft-spin relaxations navigate a continuous energy landscape before the state space hardens into a final configuration. Similarly, Ichikawa et al. initialize variables at a midpoint representing maximum uncertainty and use an annealing schedule to resolve the final discrete solution. To minimize the information loss associated with abrupt post-hoc quantization, Luo et al. employ a graduated optimization procedure that transitions smoothly from a convex relaxation to a concave objective.
Algorithmic Frameworks
Once a discrete problem is continuously relaxed, it unlocks a powerful suite of continuous optimization algorithms.
Gradient Descent and ADMM
By transforming non-differentiable logic into smooth functions, standard gradient descent becomes viable. For instance, Kyrillidis et al. introduce FourierSAT, which represents Boolean logic constraints as multilinear polynomials via Fourier expansion, allowing gradient-based algebraic solvers to solve hybrid SAT problems.
When dealing with strict structural constraints alongside relaxation, the Alternating Direction Method of Multipliers (ADMM) is highly effective. Wu et al. leverage ADMM to relax discrete bit-flipping constraints into a continuous domain, allowing gradient descent to pinpoint optimal weight bits to target during neural network adversarial attacks.
Difference of Convex (DC) Programming
When relaxations result in highly non-convex landscapes, the problem can often be split into a difference of two convex functions. Yan reformulates binary coordination constraints using DC programming, transforming a combinatorial vehicle-to-grid scheduling problem into a sequence of highly efficient convex Second-Order Cone Programs. This avoids the massive computational overhead of discrete search trees entirely.
Why It Works: An Intuitive Summary
Continuous relaxation works because it fundamentally alters how an algorithm explores a search space. In a purely discrete formulation, moving from one solution to another requires a discrete jump. There is no intermediate feedback; the algorithm cannot know if it is getting closer to a solution until it lands exactly on it.
By embedding the discrete points into a continuous space:
- The landscape becomes connected: The algorithm can compute local derivatives (gradients) that provide a compass direction toward better regions of the search space.
- Combinatorial explosion is mitigated: Highly optimized continuous solvers—which scale polynomially rather than exponentially—can be deployed to do the heavy lifting.
- Uncertainty is explicitly modeled: Variables can temporarily take on fractional values (like $0.5$) during the search, allowing the algorithm to defer hard decisions until it has gathered more global context across the optimization landscape.