Search Results

Documents authored by Solnon, Christine

Document
Invited Talk
DOI: 10.4230/LIPIcs.CP.2025.2
Anytime and Exact Search for Planning Problems: How to explore a DP-based state transition graph with A*, CP and LS? (Invited Talk)

Authors: Christine Solnon

Published in: LIPIcs, Volume 340, 31st International Conference on Principles and Practice of Constraint Programming (CP 2025)

Abstract
Many planning problems may be solved with Dynamic Programming (DP) by decomposing the problem into subproblems which are recursively solved. These decompositions induce state transition graphs which are closely related to decision diagrams [J. N. Hooker, 2013], and where optimal solutions correspond to best paths in these graphs. A* is a well known algorithm which extends Djikstra’s algorithm with heuristics for guiding the path search [Hart et al., 1968]. It is exact (provided that the heuristic function is admissible), but it is not anytime. In other words, it computes a best path but it does not output sub-optimal paths while computing it. Hence, when state transition graphs have exponential sizes, A* may run out of time or memory without producing any solution. Various anytime extensions of A* have been proposed to compute a sequence of paths of increasing quality until finding an optimal path and proving its optimality. In this talk, we will provide an overview of these exact and anytime extensions of A*, with a more detailed focus on Anytime Column Search (ACS) [Vadlamudi et al., 2012], and Iterative Memory Bounded A* (IMBA*) [L. Libralesso and F. Fontan, 2021]. Both approaches iterate A* searches while bounding the number of states that are stored or expanded at each iteration. We will also show how to combine them with Local Search (LS) in order to find better paths faster, and with bounding and constraint propagation in order to prune the graph, as proposed in [R. Fontaine et al., 2023]. This will be illustrated using the Travelling Salesman Problem (TSP) as a running example. The DP formulation introduced by Bellman in [Bellman, 1962] for the TSP has been extended to handle Time Windows (TWs) in [Christofides et al., 1981], and Time Dependent (TD) cost functions in [Malandraki and Dial, 1996]. It has also been extended to {Vehicle Routing Problems} (VRPs) in [van Hoorn, 2016] and to TD-VRPs in [Rifki et al., 2020]. We will finish by presenting an experimental comparison with state-of-the-art approaches for solving the TSP with TWs on classical benchmarks and on a new benchmark which contains hard Euclidean instances located in the phase transition zone [O. Rifki and C. Solnon, 2025].
Cite as

Christine Solnon. Anytime and Exact Search for Planning Problems: How to explore a DP-based state transition graph with A*, CP and LS? (Invited Talk). In 31st International Conference on Principles and Practice of Constraint Programming (CP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 340, pp. 2:1-2:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{solnon:LIPIcs.CP.2025.2,
  author =	{Solnon, Christine},
  title =	{{Anytime and Exact Search for Planning Problems: How to explore a DP-based state transition graph with A*, CP and LS?}},
  booktitle =	{31st International Conference on Principles and Practice of Constraint Programming (CP 2025)},
  pages =	{2:1--2:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-380-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{340},
  editor =	{de la Banda, Maria Garcia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2025.2},
  URN =		{urn:nbn:de:0030-drops-238635},
  doi =		{10.4230/LIPIcs.CP.2025.2},
  annote =	{Keywords: Dynamic Programming, A*, Anytime search, Time Dependent TSP-TW}
}
Document
DOI: 10.4230/LIPIcs.CP.2025.32
BFS-Based Canonical Codes for Generating Graphs with Constraint Programming

Authors: Xiao Peng and Christine Solnon

Published in: LIPIcs, Volume 340, 31st International Conference on Principles and Practice of Constraint Programming (CP 2025)

Abstract
We consider the problem of generating all graphs that satisfy some given additional constraints (on vertex degrees, or cycle lengths, for example). Most previous works have proposed to generate canonical codes associated with adjacency matrices. In this paper, we consider canonical codes based on Breadth First Search (BFS), and we show how to generate them with Constraint Programming (CP): we introduce a set of basic constraints that must be satisfied by all canonical codes, thus breaking many symmetries, and we introduce a global constraint to break other symmetries. We illustrate the interest of our approach on connected claw-free cubic graphs, and show that it outperforms state-of-the-art CP and SAT Modulo Theory (SMT) approaches.
Cite as

Xiao Peng and Christine Solnon. BFS-Based Canonical Codes for Generating Graphs with Constraint Programming. In 31st International Conference on Principles and Practice of Constraint Programming (CP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 340, pp. 32:1-32:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{peng_et_al:LIPIcs.CP.2025.32,
  author =	{Peng, Xiao and Solnon, Christine},
  title =	{{BFS-Based Canonical Codes for Generating Graphs with Constraint Programming}},
  booktitle =	{31st International Conference on Principles and Practice of Constraint Programming (CP 2025)},
  pages =	{32:1--32:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-380-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{340},
  editor =	{de la Banda, Maria Garcia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2025.32},
  URN =		{urn:nbn:de:0030-drops-238935},
  doi =		{10.4230/LIPIcs.CP.2025.32},
  annote =	{Keywords: Graph Generation, Automorphisms, Symmetry Breaking}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.SAT.2025.2
Anytime and Exact Search for Planning Problems: How to Explore a DP-based State Transition Graph with A*, CP and LS? (Invited Talk)

Authors: Christine Solnon

Published in: LIPIcs, Volume 341, 28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025)

Abstract
Many planning problems may be solved with Dynamic Programming (DP) by decomposing the problem into subproblems which are recursively solved. These decompositions induce state transition graphs which are closely related to decision diagrams [J. N. Hooker, 2013], and where optimal solutions correspond to best paths in these graphs. A* is a well known algorithm which extends Djikstra’s algorithm with heuristics for guiding the path search [Hart et al., 1968]. It is exact (provided that the heuristic function is admissible), but it is not anytime. In other words, it computes a best path but it does not output sub-optimal paths while computing it. Hence, when state transition graphs have exponential sizes, A* may run out of time or memory without producing any solution. Various anytime extensions of A* have been proposed to compute a sequence of paths of increasing quality until finding an optimal path and proving its optimality. In this talk, we will provide an overview of these exact and anytime extensions of A*, with a more detailed focus on Anytime Column Search (ACS) [Vadlamudi et al., 2012], and Iterative Memory Bounded A* (IMBA*) [L. Libralesso and F. Fontan, 2021]. Both approaches iterate A* searches while bounding the number of states that are stored or expanded at each iteration. We will also show how to combine them with Local Search (LS) in order to find better paths faster, and with bounding and constraint propagation in order to prune the graph, as proposed in [R. Fontaine et al., 2023]. This will be illustrated using the Travelling Salesman Problem (TSP) as a running example. The DP formulation introduced by Bellman in [Bellman, 1962] for the TSP has been extended to handle Time Windows (TWs) in [Christofides et al., 1981], and Time Dependent (TD) cost functions in [Malandraki and Dial, 1996]. It has also been extended to {Vehicle Routing Problems} (VRPs) in [van Hoorn, 2016] and to TD-VRPs in [Rifki et al., 2020]. We will finish by presenting an experimental comparison with state-of-the-art approaches for solving the TSP with TWs on classical benchmarks and on a new benchmark which contains hard Euclidean instances located in the phase transition zone [O. Rifki and C. Solnon, 2025].
Cite as

Christine Solnon. Anytime and Exact Search for Planning Problems: How to Explore a DP-based State Transition Graph with A*, CP and LS? (Invited Talk). In 28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 341, pp. 2:1-2:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{solnon:LIPIcs.SAT.2025.2,
  author =	{Solnon, Christine},
  title =	{{Anytime and Exact Search for Planning Problems: How to Explore a DP-based State Transition Graph with A*, CP and LS?}},
  booktitle =	{28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025)},
  pages =	{2:1--2:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-381-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{341},
  editor =	{Berg, Jeremias and Nordstr\"{o}m, Jakob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2025.2},
  URN =		{urn:nbn:de:0030-drops-237366},
  doi =		{10.4230/LIPIcs.SAT.2025.2},
  annote =	{Keywords: Dynamic Programming, A*, Anytime search, Time Dependent TSP-TW}
}
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
Complete Volume
DOI: 10.4230/LIPIcs.CP.2022
LIPIcs, Volume 235, CP 2022, Complete Volume

Authors: Christine Solnon

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

Abstract
LIPIcs, Volume 235, CP 2022, Complete Volume
Cite as

28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 1-692, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Proceedings{solnon:LIPIcs.CP.2022,
  title =	{{LIPIcs, Volume 235, CP 2022, Complete Volume}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{1--692},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022},
  URN =		{urn:nbn:de:0030-drops-166285},
  doi =		{10.4230/LIPIcs.CP.2022},
  annote =	{Keywords: LIPIcs, Volume 235, CP 2022, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.CP.2022.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Christine Solnon

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 0:i-0:xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{solnon:LIPIcs.CP.2022.0,
  author =	{Solnon, Christine},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{0:i--0:xviii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.0},
  URN =		{urn:nbn:de:0030-drops-166292},
  doi =		{10.4230/LIPIcs.CP.2022.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.CP.2021.40
Automatic Generation of Declarative Models For Differential Cryptanalysis

Authors: Luc Libralesso, François Delobel, Pascal Lafourcade, and Christine Solnon

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

Abstract
When designing a new symmetric block cipher, it is necessary to evaluate its robustness against differential attacks. This is done by computing Truncated Differential Characteristics (TDCs) that provide bounds on the complexity of these attacks. TDCs are often computed by using declarative approaches such as CP (Constraint Programming), SAT, or ILP (Integer Linear Programming). However, designing accurate and efficient models for these solvers is a difficult, error-prone and time-consuming task, and it requires advanced skills on both symmetric cryptography and solvers. In this paper, we describe a tool for automatically generating these models, called Tagada (Tool for Automatic Generation of Abstraction-based Differential Attacks). The input of Tagada is an operational description of the cipher by means of black-box operators and bipartite Directed Acyclic Graphs (DAGs). Given this description, we show how to automatically generate constraints that model operator semantics, and how to generate MiniZinc models. We experimentally evaluate our approach on two different kinds of differential attacks (e.g., single-key and related-key) and four different symmetric block ciphers (e.g., the AES (Advanced Encryption Standard), Craft, Midori, and Skinny). We show that our automatically generated models are competitive with state-of-the-art approaches. These automatically generated models constitute a new benchmark composed of eight optimization problems and eight enumeration problems, with instances of increasing size in each problem. We experimentally compare CP, SAT, and ILP solvers on this new benchmark.
Cite as

Luc Libralesso, François Delobel, Pascal Lafourcade, and Christine Solnon. Automatic Generation of Declarative Models For Differential Cryptanalysis. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 40:1-40:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{libralesso_et_al:LIPIcs.CP.2021.40,
  author =	{Libralesso, Luc and Delobel, Fran\c{c}ois and Lafourcade, Pascal and Solnon, Christine},
  title =	{{Automatic Generation of Declarative Models For Differential Cryptanalysis}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{40:1--40:18},
  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.40},
  URN =		{urn:nbn:de:0030-drops-153314},
  doi =		{10.4230/LIPIcs.CP.2021.40},
  annote =	{Keywords: Constraint Programming, SAT, ILP, Differential Cryptanalysis}
}
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}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact