Faster Symmetry Breaking Constraints for Abstract Structures
Constraint programming is a way of solving complex problems by stating a set of rules (called constraints) and asking a solver to find solutions that obey all of them, without ever needing to state how to solve the problem. It is useful for scheduling, planning, design, logistics problems and many other areas where many choices must satisfy many conditions at once. We look at how to find solutions faster. Many problems contain symmetries (different solutions that are effectively identical), and checking them wastes time. We propose a new method that removes these equivalent possibilities more efficiently by taking advantage of how abstract structures (such as sets, which are collections of objects where the order does not matter) are represented inside the solver. This approach performs faster than earlier techniques when dealing with indistinguishable objects (objects that are identical and hence interchangeable).
Keywords
constraint programming
Staff
Mun See Chang, Özgür Akgün, Ian P. Gent, Christopher Jefferson