💻 computer science

SAT Encodings for Bandwidth Coloring: A Systematic Design Study

This paper presents a systematic study and unified framework of six SAT encoding methods for the Bandwidth Coloring Problem, demonstrating that block encodings combined with incremental solving and symmetry breaking achieve state-of-the-art performance and solve previously intractable instances to proven optimality.

Original authors: Duc Trung Kim Nguyen, Tuyen Van Kieu, Khanh Van To

Published 2026-02-10

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Duc Trung Kim Nguyen, Tuyen Van Kieu, Khanh Van To

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the manager of a busy radio station network. You have many transmitters (let's call them "towers") scattered across a city. Each tower needs to broadcast on a specific frequency (a "color").

The rules are tricky:

No Clashing: If two towers are right next to each other, they can't use the same frequency.
Safety Buffer: If two towers are close, they don't just need different frequencies; they need frequencies that are far enough apart to avoid static and interference. The closer they are, the bigger the gap required between their frequencies.

Your goal is to use the smallest possible range of frequencies (from the lowest to the highest) to keep the whole system efficient. This is the Bandwidth Coloring Problem (BCP).

The Problem: A Puzzle Too Big for Brains

This isn't just a simple puzzle; it's a massive, complex math problem that gets exponentially harder as you add more towers. Trying to find the perfect (smallest) range by hand or with simple guesswork is impossible for large networks. Computers can try, but they often get stuck in "local loops," finding a good solution but not the best one.

The Solution: Turning the Puzzle into a "Yes/No" Game

The authors of this paper decided to translate this complex radio puzzle into a language that modern computer logic engines (called SAT solvers) are incredibly good at speaking: True/False questions.

Think of a SAT solver as a super-fast detective that answers "Yes" or "No" to a giant list of logic questions. The researchers' job was to figure out the best way to write the radio rules into these questions. They tested six different ways (encodings) to translate the problem, grouped into three styles:

The "One-Variable" Style: A simple, direct way of asking, "Is the frequency higher than X?"
The "Two-Variable" Style: A slightly more complex way that asks both "Is it higher than X?" and "Is it exactly X?" to give the detective more clues.
The "Block" Style: This is the paper's big innovation. Instead of checking every single frequency number one by one, this method groups frequencies into "blocks" (like chapters in a book). It asks, "Is the frequency in this block?" This is like checking a whole shelf of books at once instead of looking at every single book individually.

The Experiment: The Race to the Finish Line

The team ran a massive race. They took 51 different radio network maps (some easy, some incredibly hard) and ran them through all six translation styles, combined with different "helper strategies":

Incremental Solving: Instead of restarting the detective from scratch every time they lowered the frequency limit, they let the detective keep their notes and just adjust the rules slightly.
Symmetry Breaking: In these puzzles, swapping "Frequency 1" with "Frequency 2" often creates a duplicate solution. The researchers added a rule to tell the detective, "Stop checking duplicates; just pick one."

The Results: The Block Method Wins

Here is what they found, using simple terms:

The "Block" Method is the Heavyweight Champion: The "Block" encoding (specifically the one with helper notes and symmetry rules) was the fastest. It solved the hardest map in the test (called GEOM120b) in about 1,000 seconds.
The Old Champions Struggled: Previous methods (the "Order-based" styles) couldn't solve that same hard map within an hour (3,600 seconds). They got stuck.
Bigger isn't always slower: Surprisingly, the "Block" method created more questions for the computer to answer (more variables and rules) than the simpler methods. Usually, more questions mean slower answers. But here, the extra questions acted like shortcuts. They helped the detective eliminate bad paths much faster, saving time in the long run.
Helpers Matter (But Not for Everyone):
- For the "Block" method, the "Incremental" helper (keeping notes) was a huge boost.
- For the simpler "One-Variable" methods, the "Incremental" helper actually made things worse because the notes became useless when the rules changed.
- "Symmetry Breaking" helped some methods but hurt others. It's like a pair of glasses that helps one person see clearly but makes another dizzy.

The Takeaway

The paper doesn't just say "we solved it." It says, "We found the best way to translate this problem for computers."

They proved that by organizing the problem into "blocks" and using specific helper strategies, we can solve radio frequency puzzles that were previously impossible to solve perfectly. It's a reminder that in computer science, sometimes adding more structure (like the block groups) helps the machine think faster, not slower.

In short: They built a better translator for a difficult math puzzle, allowing computers to find the perfect radio frequency plan for complex networks in a fraction of the time it used to take.

Technical Summary: SAT Encodings for Bandwidth Coloring

Problem Definition

The Bandwidth Coloring Problem (BCP) is a generalization of the Graph Coloring Problem (GCP) where edges carry positive integer weights $d(u, v)$ . The objective is to assign a color $c(v) \in \mathbb{N}$ to each vertex $v$ such that the distance constraint $|c(u) - c(v)| \ge d(u, v)$ is satisfied for every edge $\{u, v\} \in E$ . The goal is to minimize the span, defined as the maximum color assigned to any vertex.

The BCP arises naturally in frequency assignment problems (FAP) for wireless and cellular networks, where vertices represent transmitters and edge weights represent minimum frequency separations required to avoid electromagnetic interference. While metaheuristic methods exist, they lack optimality guarantees. Exact methods based on Integer Linear Programming (ILP) and Constraint Programming (CP) have been studied, but ILP formulations often suffer from a constraint count that grows with edge weights. Recently, SAT-based approaches have emerged as state-of-the-art for exact solving, yet the design space for SAT encodings specifically tailored to BCP remains largely unexplored.

Methodology

The paper presents a systematic design study of SAT encodings for the BCP, proposing a unified framework that explores six distinct encoding methods organized into three categories. The framework evaluates the impact of three configurable features: incremental solving, symmetry breaking, and block width strategies.

1. Encoding Categories

The framework implements and compares the following encoding methods:

One-Variable Encodings (1G, 1L): These use ordering variables to implicitly define color assignments.
- 1G (Greater-than): Uses variables $y_{u,j}$ where $y_{u,j} = \text{true} \iff c(u) \ge j$ .
- 1L (Less-than): Uses variables $y_{u,j}$ where $y_{u,j} = \text{true} \iff c(u) \le j$ .
- These methods have an asymptotic clause count of $O(k(n+m))$ , independent of edge weights.
Two-Variable Encodings (2G, 2L): These explicitly maintain both assignment variables ( $x_{u,j}$ $x_{u, j}$ ) and ordering variables ( $y_{u,j}$ $y_{u, j}$ ) to allow for more direct distance constraints.
- 2G/2L: Similar semantics to 1G/1L but include channeling constraints linking $x$ and $y$ variables.
Block Encodings (X, Xa): These partition the color range into fixed-width blocks and use auxiliary range variables ( $R_{u,a,b}$ $R_{u, a, b}$ ) to represent sums of assignment variables within blocks.
- X: Encodes subtraction operations (required for range sums within blocks) directly without auxiliary variables.
- Xa: Introduces auxiliary variables to represent subtraction terms, allowing for clause reuse.
- Block encodings aim to reduce the number of clauses for distance constraints, particularly when edge weights are large.

2. Configurable Features

Incremental Solving: The framework tests whether reusing learned clauses across iterations (as the span upper bound decreases) improves performance. This is implemented using SAT assumptions.
Symmetry Breaking: A reflection-based technique is applied to the highest-degree vertex, restricting its color to the lower half of the span range ( $c(h) \le \lfloor k/2 \rfloor$ ). This exploits the property that if $c$ is a valid coloring, $c'(v) = k+1-c(v)$ is also valid.
Block Width Strategies: For block encodings, the framework compares fixed-width blocks (default $w=8$ ) against vary-width blocks (where width is determined by the maximum incident edge weight of a vertex).

3. Experimental Setup

The study evaluates 36 distinct configurations (combinations of the 6 methods and features) on 51 benchmark instances:

GEOM Set: 33 geometric random graphs (GEOM20 to GEOM120).
MS-CAP Set: 18 instances derived from cellular network frequency assignment problems.
Solver: CaDiCaL 1.9.5 with a 3600-second time limit per instance.
Baseline: Comparisons are made against the state-of-the-art SAT encodings POP-S-B and POPH-S-B (Faber et al., 2024).

Key Results

Overall Performance

The proposed framework achieves state-of-the-art performance. The best-performing configuration, Block Encoding Xa (with fixed width, incremental solving, and symmetry breaking), solved all 51 instances with a total time of 2721.3 seconds. This represents a 6.3% reduction in total time compared to the previous state-of-the-art POPH-S-B (2904.6s) and a 17.7% reduction compared to POP-S-B (3307.5s).

Hard Instance Performance (GEOM120b)

A critical finding concerns the hardest instance, GEOM120b:

Previous methods (POPH-S-B and POP-S-B) failed to solve GEOM120b to proven optimality within the one-hour time limit.
The proposed Block Encodings (X and Xa) solved GEOM120b to optimality in approximately 1000 seconds (specifically, the base Xa configuration solved it in 851.4s, and the fully optimized Xa in 1011.6s).
This demonstrates a speedup factor of approximately 2x over the best previous SAT-based approaches for this specific instance.

Interaction Effects

The study reveals significant interaction effects between encoding choices and solver configurations:

Incremental Solving: Provides substantial speedups for Block Encodings (e.g., 24.4% improvement for Xa) because the staircase block structure remains largely stable as the span decreases. Conversely, it offers no benefit (or slight degradation) for One-Variable Encodings (1G, 1L) because the ordering constraints are redefined relative to the new upper bound, invalidating learned clauses.
Symmetry Breaking: Its effectiveness is highly encoding-dependent. It significantly improves performance for POP-S-B (24.5% speedup) and 1L (13.2% speedup) but degrades performance for 2G (11.9% slowdown) and POPH-S-B (11.4% slowdown).
Block Width: The choice between fixed and varying block widths had minimal impact (<1.2% difference) on the 50 standard instances, suggesting that solver clause learning adapts well to both strategies.

Encoding Size vs. Efficiency

Contrary to the intuition that fewer variables and clauses yield faster solving, the Xa encoding (which generates 7x more variables and 5.5x more clauses than the most compact 1G encoding) achieved the fastest solving times. This supports the principle that auxiliary variables can strengthen unit propagation, creating "shortcuts" for the solver to derive implications more efficiently.

Significance and Claims

The paper claims that its systematic design study fills a gap in the literature regarding SAT encodings for the BCP. While symmetry breaking and incremental solving have been studied for GCP, their application and interaction with BCP-specific encodings were previously uninvestigated.

The primary contributions are:

Solving the Unsolved: The framework is the first to solve the GEOM120b benchmark to proven optimality within a reasonable time frame, a task previous exact methods could not complete in one hour.
Unified Framework: It provides a comprehensive comparative study of six encoding methods and their configurable features, identifying that Block Encodings are superior for the hardest instances, while Order-Based Encodings (like 2L and 1G) offer a favorable trade-off between implementation complexity and performance for general cases.
Interaction Insights: The work highlights that encoding features do not operate independently. Specifically, incremental solving and symmetry breaking must be selected carefully based on the specific encoding type, as they can yield synergistic or antagonistic effects.

The authors conclude that while block encodings offer the best performance on the most challenging instances, the systematic exploration of encoding design choices is essential for advancing exact BCP solvers. Future work is suggested in extending the framework to the Bandwidth MultiColoring Problem (BMCP) and developing adaptive configuration selection mechanisms.