Breaking instance-independent symmetries in exact graph coloring

Code optimization and high level synthesis can be posed as constraint satisfaction and optimization problems, such as graph coloring used in register allocation. Naturally-occurring instances of such problems are often small and can be solved optimally. A recent wave of improvements in algorithms fo...

Full description

Saved in:
Bibliographic Details
Main Authors: Ramani, A., Aloul, F.A., Markov, I.L., Sakallah, K.A.
Format: Conference Proceeding
Language:English
Subjects:
Acceleration
Constraint optimization
High level synthesis
Integer linear programming
Problem-solving
Registers
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Code optimization and high level synthesis can be posed as constraint satisfaction and optimization problems, such as graph coloring used in register allocation. Naturally-occurring instances of such problems are often small and can be solved optimally. A recent wave of improvements in algorithms for Boolean satisfiability (SAT) and 0-1 ILP suggests generic problem-reduction methods, rather than problem-specific heuristics, because: (1) heuristics are easily upset by new constraints; (2) heuristics tend to ignore structure; and (3) many relevant problems are provably inapproximable. The NP-spec project offers a language to specify NP-problems and automatic reductions to SAT. Problem reductions often lead to highly symmetric SAT instances, and symmetries are known to slow down SAT solvers. In this work, we compare several avenues for symmetry-breaking, in particular when certain kinds of symmetry are present in all generated instances. Our surprising conclusion is that instance-independent symmetries should often be processed together with instance-specific symmetries rather than earlier, at the specification level.
ISSN:1530-1591
1558-1101
DOI:10.1109/DATE.2004.1268868