Conflict Optimization for Binary CSP Applied to Minimum Partition into Plane Subgraphs and Graph Coloring

Loïc Crombez, Guilherme Dias da Fonseca, Florian Fontan, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, Luc Libralesso, Benjamin Momège, Jack Spalding-Jamieson, Brandon Zhang, Da Wei Zheng

Abstract

This paper investigates "Conflict Optimization," a metaheuristic for solving binary Constraint Satisfaction Problems (CSPs) that proved highly effective in the CG:SHOP 2022 geometry challenge. By maintaining a partial valid solution and iteratively swapping variables based on a dynamic weighting system, the authors demonstrate that this technique significantly outperforms state-of-the-art graph coloring algorithms on large-scale geometric intersection graphs. While the method excels in structured geometric environments, its performance on random graphs reveals specific limitations and highlights the importance of local structure in metaheuristic efficiency.

1. Introduction

The problem of Minimum Partition into Plane Subgraphs involves a set of straight-line segments in a 2D plane. The objective is to partition these segments into the minimum number of sets such that no two segments in any single set intersect. Mathematically, this is a specific instance of the Vertex Coloring problem applied to an intersection graph: each segment represents a vertex, and an edge exists between two vertices if their corresponding segments cross.

While graph coloring is a classic NP-hard problem, geometric intersection graphs present unique challenges. They often contain tens of thousands of vertices and exhibit high density and specific structural properties (such as large cliques). Traditional exact solvers and standard greedy heuristics frequently struggle with these instances. This paper formalizes the "Conflict Optimization" strategy that emerged as the dominant approach among the top-performing teams in the CG:SHOP 2022 competition.

2. Methodology: The Conflict Optimization Metaheuristic

Conflict Optimization is a local search metaheuristic designed for binary CSPs. Its defining characteristic is the maintenance of a partial but valid assignment. Unlike many local search algorithms that maintain a complete assignment and attempt to minimize the number of violated constraints, Conflict Optimization ensures that the currently "colored" portion of the graph is always valid.

2.1 The Core Algorithm

The algorithm operates through an iterative process of reassignment and weight adjustment:

  1. Initialization: A valid initial coloring is generated, often using a greedy heuristic. One entire color class is then removed, and its vertices are placed into a "conflict set" $S$.
  2. Selection: A vertex $v$ is selected from the conflict set $S$.
  3. Reassignment: For every available color, the algorithm calculates a "conflict score." This score is defined as the sum of the weights $w(u)$ of all currently colored vertices $u$ that would conflict with $v$ if $v$ were assigned that color.
  4. The Swap: Vertex $v$ is assigned the color with the lowest conflict score. Any vertices that now conflict with $v$ are removed from their color classes and added to the conflict set $S$.
  5. Dynamic Weighting: To prevent infinite loops and encourage exploration, the weight of a vertex increases every time it is removed from a color class. The weight is typically calculated as $w(u) = 1 + q(u)^p$, where $q(u)$ is the number of times the vertex has been uncolored and $p$ is a hyperparameter.

2.2 Implementation Variants

The paper highlights specific enhancements introduced by the leading competition teams:

  • Team Lasa: Utilized "Orientation Greedy" initialization, which sorts segments by their angle to exploit the geometric nature of the input.
  • Team Gitastrophe: Implemented an intensification/diversification phase that toggles the objective function between minimizing raw conflicts and the standard weighted score.
  • Team Shadoks: Introduced Bounded Depth-First Search (BDFS) to check if a vertex could be recolored by shifting a small number of neighbors. They also used Degeneracy Ordering to remove "easy" vertices before the main optimization phase.

3. Experimental Evaluation

The study evaluated these algorithms using two primary benchmarks: the 225 geometric instances from CG:SHOP 2022 and the classic DIMACS general graph coloring benchmarks.

3.1 Performance on Geometric Graphs

On geometric intersection graphs, Conflict Optimization demonstrated clear dominance. For example, on the vispecn13806 instance, the state-of-the-art HEAD algorithm (a general-purpose graph colorer) required an hour to find a solution with 283 colors. In contrast, Conflict Optimization implementations reached solutions with fewer than 220 colors in the same timeframe. Furthermore, the teams were often able to prove optimality by identifying cliques within the graphs that matched the final color count.

3.2 Performance on General Graphs (DIMACS)

Results on the DIMACS benchmark were mixed. The algorithm performed "extremely poorly" on random graphs, where the lack of local structure prevents the metaheuristic from making meaningful progress. However, it matched or exceeded best-known results on geometric-like DIMACS instances, such as the r* and dsjr* series, suggesting that the algorithm's strength lies in exploiting non-random connectivity patterns.

4. Discussion and Key Insights

The success of Conflict Optimization is attributed to its "partial validity" approach. By ensuring the colored portion of the graph is always valid, the algorithm effectively defers conflicts. The dynamic weighting mechanism ensures that no single vertex can be displaced indefinitely, forcing the solver to explore new regions of the search space.

The exponent $p$ in the weight function is a critical hyperparameter. Research by Team Shadoks suggests that $p=1.2$ provides an ideal balance—high enough to avoid cycles but low enough to allow the algorithm to intensify its search in promising areas.

5. Conclusion and Future Work

Conflict Optimization is a powerful tool for solving large-scale, structured binary CSPs. While it is less effective on random graphs, its performance on geometric instances sets a new benchmark for the field. Future research may explore adapting this technique for non-binary CSPs and further hybridizing the metaheuristic with BDFS or other local search techniques to handle complex reassignments more efficiently.

Summary updated

BibTeX
@article{crombez2023conflict,
  author = {Loïc Crombez and Guilherme Dias da Fonseca and Florian Fontan and Yan Gerard and Aldo Gonzalez-Lorenzo and Pascal Lafourcade and Luc Libralesso and Benjamin Momège and Jack Spalding-Jamieson and Brandon Zhang and Da Wei Zheng},
  title = {{Conflict Optimization for Binary CSP Applied to Minimum Partition into Plane Subgraphs and Graph Coloring}},
  journal = {ACM J. Exp. Algorithmics},
  year = {2023},
  doi = {10.1145/3588869},
}
Figure