DROPS

Document

DOI: 10.4230/LIPIcs.CP.2023.28

Using Canonical Codes to Efficiently Solve the Benzenoid Generation Problem with Constraint Programming

Authors: Xiao Peng and Christine Solnon

Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)

Abstract

The Benzenoid Generation Problem (BGP) aims at generating all benzenoid molecules that satisfy some given properties. This problem has important applications in chemistry, and Carissan et al (2021) have shown us that Constraint Programming (CP) is well suited for modelling this problem because properties defined by chemists are easy to express by means of constraints. Benzenoids are described by hexagon graphs and a key point for an efficient enumeration of these graphs is to be invariant to rotations and symmetries. In this paper, we introduce canonical codes that uniquely characterise hexagon graphs while being invariant to rotations and symmetries. We show that these codes may be defined by means of constraints. We also introduce a global constraint for ensuring that codes are canonical, and a global constraint for ensuring that a pattern is included in a code. We experimentally compare our new CP model with the CP-based approach of Carissan et al (2021), and we show that it has better scale-up properties.

Cite as

Xiao Peng and Christine Solnon. Using Canonical Codes to Efficiently Solve the Benzenoid Generation Problem with Constraint Programming. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{peng_et_al:LIPIcs.CP.2023.28,
  author =	{Peng, Xiao and Solnon, Christine},
  title =	{{Using Canonical Codes to Efficiently Solve the Benzenoid Generation Problem with Constraint Programming}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{28:1--28:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.28},
  URN =		{urn:nbn:de:0030-drops-190650},
  doi =		{10.4230/LIPIcs.CP.2023.28},
  annote =	{Keywords: Benzenoid Generation Problem, Canonical Code, Hexagon Graph}
}

Document

DOI: 10.4230/LIPIcs.CP.2021.45

Solving the Non-Crossing MAPF with CP

Authors: Xiao Peng, Christine Solnon, and Olivier Simonin

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)

Abstract

We introduce a new Multi-Agent Path Finding (MAPF) problem which is motivated by an industrial application. Given a fleet of robots that move on a workspace that may contain static obstacles, we must find paths from their current positions to a set of destinations, and the goal is to minimise the length of the longest path. The originality of our problem comes from the fact that each robot is attached with a cable to an anchor point, and that robots are not able to cross these cables. We formally define the Non-Crossing MAPF (NC-MAPF) problem and show how to compute lower and upper bounds by solving well known assignment problems. We introduce a Variable Neighbourhood Search (VNS) approach for improving the upper bound, and a Constraint Programming (CP) model for solving the problem to optimality. We experimentally evaluate these approaches on randomly generated instances.

Cite as

Xiao Peng, Christine Solnon, and Olivier Simonin. Solving the Non-Crossing MAPF with CP. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 45:1-45:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{peng_et_al:LIPIcs.CP.2021.45,
  author =	{Peng, Xiao and Solnon, Christine and Simonin, Olivier},
  title =	{{Solving the Non-Crossing MAPF with CP}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{45:1--45:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.45},
  URN =		{urn:nbn:de:0030-drops-153367},
  doi =		{10.4230/LIPIcs.CP.2021.45},
  annote =	{Keywords: Constraint Programming (CP), Multi-Agent Path Finding (MAPF), Assignment Problems}
}

Search Results

Documents authored by Peng, Xiao

Using Canonical Codes to Efficiently Solve the Benzenoid Generation Problem with Constraint Programming

Abstract

Cite as

Solving the Non-Crossing MAPF with CP

Abstract

Cite as

Thanks for your feedback!

Could not send message