Search Results

Documents authored by Schaus, Pierre

Document
DOI: 10.4230/LIPIcs.CP.2026.16
An Offline Neuro-Symbolic Football Pattern Retrieval Approach Using Constraint Programming

Authors: Augustin Crespin and Pierre Schaus

Published in: LIPIcs, Volume 379, 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)

Abstract
Using a single broadcast camera, modern deep learning methods can detect and label players and ball positions on a frame-by-frame basis. This work focuses on post-game analysis, where frame-level labels are available for the entire video sequence. Deep learning alone performs poorly when retrieving intervals of frames in which specific spatio-temporal conditions or tactical patterns occur involving players and ball positions. A loosely coupled neuro-symbolic approach is proposed, in which these precomputed frame-level detections are processed through an SQL-like domain-specific query language. Each query is compiled into a Constraint Programming (CP) model that retrieves intervals of frames satisfying the specified constraints. The method leverages well-established CP constructs, such as time intervals and regular constraints. Experiments on real football games demonstrate that this approach is simple and efficient, enabling expressive querying for post-game tactical analysis while remaining accurate and scalable.
Cite as

Augustin Crespin and Pierre Schaus. An Offline Neuro-Symbolic Football Pattern Retrieval Approach Using Constraint Programming. In 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 379, pp. 16:1-16:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{crespin_et_al:LIPIcs.CP.2026.16,
  author =	{Crespin, Augustin and Schaus, Pierre},
  title =	{{An Offline Neuro-Symbolic Football Pattern Retrieval Approach Using Constraint Programming}},
  booktitle =	{32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)},
  pages =	{16:1--16:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-432-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{379},
  editor =	{Beldiceanu, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2026.16},
  URN =		{urn:nbn:de:0030-drops-266491},
  doi =		{10.4230/LIPIcs.CP.2026.16},
  annote =	{Keywords: Pattern Matching, Domain-Specific Language, Video Analysis}
}
Document
DOI: 10.4230/LIPIcs.CP.2026.23
Assembly Line Balancing with Parallel Stations and Shared Resources: A Cycle-Relative Constraint Programming Approach

Authors: Diego Olivier Fernandez Pons and Pierre Schaus

Published in: LIPIcs, Volume 379, 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)

Abstract
This paper addresses an assembly line balancing problem that combines task assignment, scheduling, and allocation of parallel workstations to minimize cycle time, subject to precedence and shared resource constraints. A key complexity in periodic production environments is the presence of cyclic resource constraints which arise when workers (resources) move between workstations within the same cycle. This scenario is particularly prevalent in large-scale manufacturing industries with long cycle times, such as aerospace assembly. Existing constraint programming (CP) models for this problem schedule tasks on an absolute time horizon. However, this approach relies on modulo operators to project task intervals into a cycle window, which hinders constraint propagation, and makes extending the model beyond fixed factory layouts difficult. We propose a novel cycle-relative CP formulation that addresses both shortcomings. Our model dynamically determines the optimal placement of parallel workstations and defines task decision variables directly within the cycle window, eliminating the need for modulo operators. Experimental evaluations demonstrate the cycle-relative model’s superiority, consistently finding equal or better solutions faster than the temporal approach. Furthermore, a direct engine comparison shows that OptalCP outperforms CP Optimizer on these models across the vast majority of instances.
Cite as

Diego Olivier Fernandez Pons and Pierre Schaus. Assembly Line Balancing with Parallel Stations and Shared Resources: A Cycle-Relative Constraint Programming Approach. In 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 379, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fernandezpons_et_al:LIPIcs.CP.2026.23,
  author =	{Fernandez Pons, Diego Olivier and Schaus, Pierre},
  title =	{{Assembly Line Balancing with Parallel Stations and Shared Resources: A Cycle-Relative Constraint Programming Approach}},
  booktitle =	{32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)},
  pages =	{23:1--23:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-432-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{379},
  editor =	{Beldiceanu, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2026.23},
  URN =		{urn:nbn:de:0030-drops-266784},
  doi =		{10.4230/LIPIcs.CP.2026.23},
  annote =	{Keywords: Constraint programming, line-balancing, cyclic scheduling, rcpsp}
}
Document
DOI: 10.4230/LIPIcs.CP.2026.49
The Distance Constraint on Sequence Variables

Authors: Margaux Schmied, Augustin Delecluse, Jean-Charles Régin, and Pierre Schaus

Published in: LIPIcs, Volume 379, 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)

Abstract
Insertion sequence variables have recently been introduced as a computational domain for modeling routing and sequencing problems in constraint programming. Typically, search heuristics guide the insertion process of new nodes into a partial growing path, while constraints eliminate infeasible insertions. This paper investigates filtering for the (minimum) distance constraint over insertion sequence variables. This global constraint links a sequence to a distance variable based on a given distance matrix. So far, only a simple filtering algorithm has been proposed, which considers the partial path but ignores mandatory nodes. Our contribution is to introduce stronger lower bounds that also take mandatory nodes into account. These bounds further enable the derivation of additional filtering rules for node insertions. An experimental evaluation on the TourMustSee problem shows that the proposed filtering rules significantly reduce the search space compared to the existing filtering approach.
Cite as

Margaux Schmied, Augustin Delecluse, Jean-Charles Régin, and Pierre Schaus. The Distance Constraint on Sequence Variables. In 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 379, pp. 49:1-49:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{schmied_et_al:LIPIcs.CP.2026.49,
  author =	{Schmied, Margaux and Delecluse, Augustin and R\'{e}gin, Jean-Charles and Schaus, Pierre},
  title =	{{The Distance Constraint on Sequence Variables}},
  booktitle =	{32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)},
  pages =	{49:1--49:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-432-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{379},
  editor =	{Beldiceanu, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2026.49},
  URN =		{urn:nbn:de:0030-drops-266828},
  doi =		{10.4230/LIPIcs.CP.2026.49},
  annote =	{Keywords: Constraint programming, sequence variable, global constraint, cost-based constraint, distance constraint, lower bound}
}
Artifact
Software
DOI: 10.4230/artifacts.24098
composite_structure

Authors: Miguel Antoons, Augustin Delecluse, Samih Zein, and Pierre Schaus

Abstract
Cite as

Miguel Antoons, Augustin Delecluse, Samih Zein, Pierre Schaus. composite_structure (Software, Source code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-24098,
   title = {{composite\underlinestructure}}, 
   author = {Antoons, Miguel and Delecluse, Augustin and Zein, Samih and Schaus, Pierre},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:6a1da259835bc6788634d1ba52bda3a11d8b03b1;origin=https://github.com/augustindelecluse/composite_structure;visit=swh:1:snp:299c712378c96992f4a33ce2f58a9294e30cc5b0;anchor=swh:1:rev:cfb5ddced13153d5add98f58a5719205e8f94da9}{\texttt{swh:1:dir:6a1da259835bc6788634d1ba52bda3a11d8b03b1}} (visited on 2025-08-08)},
   url = {https://github.com/augustindelecluse/composite_structure},
   doi = {10.4230/artifacts.24098},
}
Document
Short Paper
DOI: 10.4230/LIPIcs.CP.2025.41
Modeling and Solving a Composite Structure Design Problem with Constraint Programming (Short Paper)

Authors: Miguel Antoons, Augustin Delecluse, Samih Zein, and Pierre Schaus

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

Abstract
Composite structures are composed of plies (layers) of carbon fibers. For each ply, one must decide its orientation from the set of possible angles: -45°, 0°, 45°, and 90°. The stack of plies must follow strict constraints on the chosen orientations to achieve mechanical properties of the composite, such as sufficient buckling load. The design problem becomes more complex when determining the stack of plies for a complete surface material, that does not require the same number of plies in every region of the surface. Not only must the orientations be selected in each region, but it is also necessary to decide which plies are discontinued between adjacent regions. Thanks to its declarative nature, Constraint Programming (CP) offers an elegant modeling of the constraints, making it easy for designers to activate or deactivate them as needed. We propose a CP model, implemented in MiniZinc. The performance of this model on synthetic yet realistic instances when solved by different exact solvers, including Mixed Integer Programming (MIP) solvers, demonstrates the superiority of CP over MIP on our MiniZinc model, and over a commercial solution implemented by an industrial partner. It opens up the adoption of CP as an efficient building block of Computer-Aided Design tools for composite structures. By making the model and instances publicly available, we also hope to facilitate the inclusion of this problem in CP solver competitions and stimulate further research in this area.
Cite as

Miguel Antoons, Augustin Delecluse, Samih Zein, and Pierre Schaus. Modeling and Solving a Composite Structure Design Problem with Constraint Programming (Short Paper). In 31st International Conference on Principles and Practice of Constraint Programming (CP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 340, pp. 41:1-41:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{antoons_et_al:LIPIcs.CP.2025.41,
  author =	{Antoons, Miguel and Delecluse, Augustin and Zein, Samih and Schaus, Pierre},
  title =	{{Modeling and Solving a Composite Structure Design Problem with Constraint Programming}},
  booktitle =	{31st International Conference on Principles and Practice of Constraint Programming (CP 2025)},
  pages =	{41:1--41:9},
  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.41},
  URN =		{urn:nbn:de:0030-drops-239022},
  doi =		{10.4230/LIPIcs.CP.2025.41},
  annote =	{Keywords: Constraint Programming, Composite Structures, Design Rules, MiniZinc}
}
Document
DOI: 10.4230/LIPIcs.CP.2024.10
Anytime Weighted Model Counting with Approximation Guarantees for Probabilistic Inference

Authors: Alexandre Dubray, Pierre Schaus, and Siegfried Nijssen

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)

Abstract
Weighted model counting (WMC) plays a central role in probabilistic reasoning. Given that this problem is #P-hard, harder instances can generally only be addressed using approximate techniques based on sampling, which provide statistical convergence guarantees: the longer a sampling process runs, the more accurate the WMC is likely to be. In this work, we propose a deterministic search-based approach that can also be stopped at any time and provides hard lower- and upper-bound guarantees on the true WMC. This approach uses a value heuristic that guides exploration first towards models with a high weight and leverages Limited Discrepancy Search to make the bounds converge faster. The validity, scalability, and convergence of our approach are tested and compared with state-of-the-art baseline methods on the problem of computing marginal probabilities in Bayesian networks and reliability estimation in probabilistic graphs.
Cite as

Alexandre Dubray, Pierre Schaus, and Siegfried Nijssen. Anytime Weighted Model Counting with Approximation Guarantees for Probabilistic Inference. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dubray_et_al:LIPIcs.CP.2024.10,
  author =	{Dubray, Alexandre and Schaus, Pierre and Nijssen, Siegfried},
  title =	{{Anytime Weighted Model Counting with Approximation Guarantees for Probabilistic Inference}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.10},
  URN =		{urn:nbn:de:0030-drops-206956},
  doi =		{10.4230/LIPIcs.CP.2024.10},
  annote =	{Keywords: Projected Weighted Model Counting, Limited Discrepancy Search, Approximate Method, Probabilistic Inference}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.CP.2024.36
Black-Box Value Heuristics for Solving Optimization Problems with Constraint Programming (Short Paper)

Authors: Augustin Delecluse and Pierre Schaus

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)

Abstract
Significant research efforts have focused on black-box variable selection, with less attention given to value heuristics. An ideal value heuristic enables depth-first-search to prioritize high-quality solutions first. The Bound-Impact Value Selection achieves this goal through a look-ahead strategy, trying every value of the selected variable and ranking them based on their impact on the objective. However, this method is generally too computationally intensive for the entire search tree. We introduce two simple yet powerful modifications to improve its scalability. First, a lighter fix point computation involving only the constraints on the shortest path in the constraint graph between the variable and the objective. Second, a reverse look-ahead strategy optimistically fixes the objective variable to its minimum in order to prioritize the remaining values. These two ideas have been empirically validated on a range of academic problems and in the XCSP³ competition, demonstrating significant improvements in scalability.
Cite as

Augustin Delecluse and Pierre Schaus. Black-Box Value Heuristics for Solving Optimization Problems with Constraint Programming (Short Paper). In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 36:1-36:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{delecluse_et_al:LIPIcs.CP.2024.36,
  author =	{Delecluse, Augustin and Schaus, Pierre},
  title =	{{Black-Box Value Heuristics for Solving Optimization Problems with Constraint Programming}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{36:1--36:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.36},
  URN =		{urn:nbn:de:0030-drops-207214},
  doi =		{10.4230/LIPIcs.CP.2024.36},
  annote =	{Keywords: Constraint Programming, Value Selection, Look-Ahead, Optimization}
}
Document
DOI: 10.4230/LIPIcs.CP.2023.13
Boosting Decision Diagram-Based Branch-And-Bound by Pre-Solving with Aggregate Dynamic Programming

Authors: Vianney Coppé, Xavier Gillard, and Pierre Schaus

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

Abstract
Discrete optimization problems expressible as dynamic programs can be solved by branch-and-bound with decision diagrams. This approach dynamically compiles bounded-width decision diagrams to derive both lower and upper bounds on unexplored parts of the search space, until they are all enumerated or discarded. Assuming a minimization problem, relaxed decision diagrams provide lower bounds through state merging while restricted decision diagrams obtain upper bounds by excluding states to limit their size. As the selection of states to merge or delete is done locally, it is very myopic to the global problem structure. In this paper, we propose a novel way to proceed that is based on pre-solving a so-called aggregate version of the problem with a limited number of states. The compiled decision diagram of this aggregate problem is tractable and can fit in memory. It can then be exploited by the original branch-and-bound to generate additional pruning and guide the compilation of restricted decision diagrams toward good solutions. The results of the numerical study we conducted on three combinatorial optimization problems show a clear improvement in the performance of DD-based solvers when blended with the proposed techniques. These results also suggest an approach where the aggregate dynamic programming model could be used in replacement of the relaxed decision diagrams altogether.
Cite as

Vianney Coppé, Xavier Gillard, and Pierre Schaus. Boosting Decision Diagram-Based Branch-And-Bound by Pre-Solving with Aggregate Dynamic Programming. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{coppe_et_al:LIPIcs.CP.2023.13,
  author =	{Copp\'{e}, Vianney and Gillard, Xavier and Schaus, Pierre},
  title =	{{Boosting Decision Diagram-Based Branch-And-Bound by Pre-Solving with Aggregate Dynamic Programming}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{13:1--13: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.13},
  URN =		{urn:nbn:de:0030-drops-190500},
  doi =		{10.4230/LIPIcs.CP.2023.13},
  annote =	{Keywords: Discrete Optimization, Decision Diagrams, Aggregate Dynamic Programming}
}
Document
DOI: 10.4230/LIPIcs.CP.2023.15
Probabilistic Inference by Projected Weighted Model Counting on Horn Clauses

Authors: Alexandre Dubray, Pierre Schaus, and Siegfried Nijssen

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

Abstract
Weighted model counting, that is, counting the weighted number of satisfying assignments of a propositional formula, is an important tool in probabilistic reasoning. Recently, the use of projected weighted model counting (PWMC) has been proposed as an approach to formulate and answer probabilistic queries. In this work, we propose a new simplified modeling language based on PWMC in which probabilistic inference tasks are modeled using a conjunction of Horn clauses and a particular weighting scheme for the variables. We show that the major problems of inference for Bayesian Networks, network reachability and probabilistic logic programming can be modeled in this language. Subsequently, we propose a new, relatively simple solver that is specifically optimized to solve the PWMC problem for such formulas. Our experiments show that our new solver is competitive with state-of-the-art solvers on the major problems studied.
Cite as

Alexandre Dubray, Pierre Schaus, and Siegfried Nijssen. Probabilistic Inference by Projected Weighted Model Counting on Horn Clauses. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{dubray_et_al:LIPIcs.CP.2023.15,
  author =	{Dubray, Alexandre and Schaus, Pierre and Nijssen, Siegfried},
  title =	{{Probabilistic Inference by Projected Weighted Model Counting on Horn Clauses}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{15:1--15: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.15},
  URN =		{urn:nbn:de:0030-drops-190520},
  doi =		{10.4230/LIPIcs.CP.2023.15},
  annote =	{Keywords: Model Counting, Bayesian Networks, Probabilistic Networks}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.CP.2023.45
Partitioning a Map into Homogeneous Contiguous Regions: A Branch-And-Bound Approach Using Decision Diagrams (Short Paper)

Authors: Nicolas Golenvaux, Xavier Gillard, Siegfried Nijssen, and Pierre Schaus

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

Abstract
Regionalization is a crucial spatial analysis technique used for partitioning a map divided into zones into k continuous areas, optimizing the similarity of zone attributes within each area. This technique has a variety of applications in fields like urban planning, environmental management, and geographic information systems. The REDCAP algorithm is a well-known approach for addressing the regionalization problem. It consists of two main steps: first, it generates a spatially contiguous tree (SCT) representing the neighborhood structure of the set of spatial objects using a contiguity-constrained hierarchical clustering method. Second, it greedily removes k-1 edges from the SCT to create k regions. While this approach has proven to be effective, it may not always produce the most optimal solutions. We propose an alternative method for the second step, an exact dynamic programming (DP) formulation for the k-1 edges removal problem. This DP is solved using a multi-valued decision diagram (MDD)-based branch and bound solver leading to a more optimal solution. We compared our proposed method with the REDCAP state-of-the-art technique on real data and synthetic ones, using different instances of the regionalization problem and different supervised and unsupervised metrics. Our results indicate that our approach provides higher quality partitions than those produced by REDCAP at acceptable computational costs. This suggests that our method could be a viable alternative for addressing the regionalization problem in various applications.
Cite as

Nicolas Golenvaux, Xavier Gillard, Siegfried Nijssen, and Pierre Schaus. Partitioning a Map into Homogeneous Contiguous Regions: A Branch-And-Bound Approach Using Decision Diagrams (Short Paper). In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 45:1-45:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{golenvaux_et_al:LIPIcs.CP.2023.45,
  author =	{Golenvaux, Nicolas and Gillard, Xavier and Nijssen, Siegfried and Schaus, Pierre},
  title =	{{Partitioning a Map into Homogeneous Contiguous Regions: A Branch-And-Bound Approach Using Decision Diagrams}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{45:1--45:10},
  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.45},
  URN =		{urn:nbn:de:0030-drops-190825},
  doi =		{10.4230/LIPIcs.CP.2023.45},
  annote =	{Keywords: Regionalization, Redcap, Skater, Multivalued Decision Diagrams}
}
Document
DOI: 10.4230/LIPIcs.CP.2022.14
Solving the Constrained Single-Row Facility Layout Problem with Decision Diagrams

Authors: Vianney Coppé, Xavier Gillard, and Pierre Schaus

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

Abstract
The Single-Row Facility Layout Problem is an NP-hard problem dealing with the ordering of departments with given lengths and pairwise traffic intensities in a facility. In this context, one seeks to minimize the sum of the distances between department pairs, weighted by the corresponding traffic intensities. Practical applications of this problem include the arrangement of rooms on a corridor in hospitals or offices, airplanes and gates in an airport or machines in a manufacture. This paper presents two novel exact models for the Constrained Single-Row Facility Layout Problem, a recent variant of the problem including positioning, ordering and adjacency constraints. On the one hand, the state-of-the-art mixed-integer programming model for the unconstrained problem is extended to incorporate the constraints. On the other hand, a decision diagram-based approach is described, based on an existing dynamic programming model for the unconstrained problem. Computational experiments show that both models outperform the only mixed-integer programming model in the literature, to the best of our knowledge. While the two models have execution times of the same order of magnitude, the decision diagram-based approach handles positioning constraints much better but the mixed-integer programming model has the advantage for ordering constraints.
Cite as

Vianney Coppé, Xavier Gillard, and Pierre Schaus. Solving the Constrained Single-Row Facility Layout Problem with Decision Diagrams. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{coppe_et_al:LIPIcs.CP.2022.14,
  author =	{Copp\'{e}, Vianney and Gillard, Xavier and Schaus, Pierre},
  title =	{{Solving the Constrained Single-Row Facility Layout Problem with Decision Diagrams}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{14:1--14:18},
  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.14},
  URN =		{urn:nbn:de:0030-drops-166433},
  doi =		{10.4230/LIPIcs.CP.2022.14},
  annote =	{Keywords: Discrete Optimization, Mixed-Integer Programming, Decision Diagrams, Constrained Single-Row Facility Layout Problem}
}
Document
DOI: 10.4230/LIPIcs.CP.2022.19
Sequence Variables for Routing Problems

Authors: Augustin Delecluse, Pierre Schaus, and Pascal Van Hentenryck

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

Abstract
Constraint Programming (CP) is one of the most flexible approaches for modeling and solving vehicle routing problems (VRP). This paper proposes the sequence variable domain, that is inspired by the insertion graph introduced in [Bent and Van Hentenryck, 2004] and the subset bound domain for set variables. This domain representation, which targets VRP applications, allows for an efficient insertion-based search on a partial tour and the implementation of simple, yet efficient filtering algorithms for constraints that enforce time-windows on the visits and capacities on the vehicles. Experiment results demonstrate the efficiency and flexibility of this CP domain for solving some hard VRP problems, including the Dial-A-Ride, the Patient Transportation, and the asymmetric TSP with time windows.
Cite as

Augustin Delecluse, Pierre Schaus, and Pascal Van Hentenryck. Sequence Variables for Routing Problems. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 19:1-19:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{delecluse_et_al:LIPIcs.CP.2022.19,
  author =	{Delecluse, Augustin and Schaus, Pierre and Van Hentenryck, Pascal},
  title =	{{Sequence Variables for Routing Problems}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{19:1--19:17},
  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.19},
  URN =		{urn:nbn:de:0030-drops-166485},
  doi =		{10.4230/LIPIcs.CP.2022.19},
  annote =	{Keywords: Constraint Programming, Dial-A-Ride, Patient Transportation, TSPTW, Vehicle Routing, Sequence Variables, Insertion Variables}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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