## Abstract

Breaking symmetries is crucial when solving hard combinatorial problems. A common way to eliminate symmetries in CP/SAT is to add symmetry breaking constraints. Ideally, symmetry breaking constraints should be complete and compact. The aim of this paper is to find compact and complete symmetry breaks applicable when solving hard combinatorial problems using CP/SAT approach. In particular: graph search problems and matrix model problems where symmetry breaks are often specified in terms of lex constraints. We show that sets of lex constraints can be expressed with only a small portion of their inner lex implications which are a particular form of Horn clauses. We exploit this fact and compute a compact encoding of the row-wise LexLeader and state of the art partial symmetry breaking constraints. We illustrate the approach for graph search problems and matrix model problems.

Original language | English |
---|---|

Title of host publication | Functional and Logic Programming |

Subtitle of host publication | 14th International Symposium, FLOPS 2018 Nagoya, Japan, May 9–11, 2018 Proceedings |

Editors | John P. Gallagher, Martin Sulzmann |

Place of Publication | Cham Switzerland |

Publisher | Springer |

Pages | 182-197 |

Number of pages | 16 |

ISBN (Electronic) | 978-3-319-90686-7 |

ISBN (Print) | 9783319906850 |

DOIs | |

Publication status | Published - 2018 |

Externally published | Yes |

Event | International Symposium on Functional and Logic Programming 2018 - Nagoya, Japan Duration: 9 May 2018 → 11 May 2018 Conference number: 14th http://www.sqlab.jp/FLOPS2018/ |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer |

Volume | 10818 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | International Symposium on Functional and Logic Programming 2018 |
---|---|

Abbreviated title | FLOPS 2018 |

Country | Japan |

City | Nagoya |

Period | 9/05/18 → 11/05/18 |

Internet address |