Search Results

Documents authored by Beck, J. Christopher

Artifact
Software
DOI: 10.4230/artifacts.24205
RPID

Authors: Ryo Kuroiwa and J. Christopher Beck

Abstract
Cite as

Ryo Kuroiwa, J. Christopher Beck. RPID (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-24205,
   title = {{RPID}}, 
   author = {Kuroiwa, Ryo and Beck, J. Christopher},
   note = {Software, version 0.1.0., swhId: \href{https://archive.softwareheritage.org/swh:1:dir:9f071b7f5f3daf914c19752ae76692b3a8d1b108;origin=https://github.com/domain-independent-dp/rpid;visit=swh:1:snp:f70c29e2311a12e68fcd938ca0b5d26a248262ce;anchor=swh:1:rev:240549a24194f89ae28f745303df217bc57b6760}{\texttt{swh:1:dir:9f071b7f5f3daf914c19752ae76692b3a8d1b108}} (visited on 2025-08-08)},
   url = {https://github.com/domain-independent-dp/rpid},
   doi = {10.4230/artifacts.24205},
}
Artifact
Software
DOI: 10.4230/artifacts.23555
Travelling Salesperson Problem with Self Deleting Graphs

Authors: Daniel Pekar and J. Christopher Beck

Abstract
Cite as

Daniel Pekar, J. Christopher Beck. Travelling Salesperson Problem with Self Deleting Graphs (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-23555,
   title = {{Travelling Salesperson Problem with Self Deleting Graphs}}, 
   author = {Pekar, Daniel and Beck, J. Christopher},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:c287b1067c276693ca630e6e6f7a18daf1a90d38;origin=https://github.com/uoft-tidel/tsp-sd;visit=swh:1:snp:80da2bba26c2bc64c9fbc04ae205e4b98c1a9a3b;anchor=swh:1:rev:7b6bd841d633ecb2ccbb9b7e4022639fe258ae30}{\texttt{swh:1:dir:c287b1067c276693ca630e6e6f7a18daf1a90d38}} (visited on 2025-08-08)},
   url = {https://github.com/uoft-tidel/tsp-sd},
   doi = {10.4230/artifacts.23555},
}
Document
DOI: 10.4230/LIPIcs.CP.2025.5
Transition Dominance in Domain-Independent Dynamic Programming

Authors: J. Christopher Beck, Ryo Kuroiwa, Jimmy H. M. Lee, Peter J. Stuckey, and Allen Z. Zhong

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

Abstract
Domain-independent dynamic programming (DIDP) is a model-based paradigm for dynamic programming (DP) that enables users to define DP models based on a state transition system. Heuristic search-based solvers have demonstrated strong performance in solving combinatorial optimization problems. In this paper, we formally define transition dominance in DIDP, where one transition consistently leads to better solutions than another, allowing the search process to safely ignore dominated transitions. To facilitate the efficient use of transition dominance, we introduce an interface for defining transition dominance and propose the use of state functions to cache values, thereby avoiding redundant computations when verifying transition dominance. Experimental results on DP models across multiple problem classes indicate that incorporating transition dominance and state functions yields a 5 to 10 times speed-up on average for different search algorithms within the DIDP framework compared to the baseline.
Cite as

J. Christopher Beck, Ryo Kuroiwa, Jimmy H. M. Lee, Peter J. Stuckey, and Allen Z. Zhong. Transition Dominance in Domain-Independent Dynamic Programming. In 31st International Conference on Principles and Practice of Constraint Programming (CP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 340, pp. 5:1-5:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{beck_et_al:LIPIcs.CP.2025.5,
  author =	{Beck, J. Christopher and Kuroiwa, Ryo and Lee, Jimmy H. M. and Stuckey, Peter J. and Zhong, Allen Z.},
  title =	{{Transition Dominance in Domain-Independent Dynamic Programming}},
  booktitle =	{31st International Conference on Principles and Practice of Constraint Programming (CP 2025)},
  pages =	{5:1--5:23},
  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.5},
  URN =		{urn:nbn:de:0030-drops-238661},
  doi =		{10.4230/LIPIcs.CP.2025.5},
  annote =	{Keywords: Dominance, Dynamic Programming, Combinatorial Optimization}
}
Document
DOI: 10.4230/LIPIcs.CP.2025.23
RPID: Rust Programmable Interface for Domain-Independent Dynamic Programming

Authors: Ryo Kuroiwa and J. Christopher Beck

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

Abstract
In domain-independent dynamic programming (DIDP), a problem is formulated as a dynamic programming (DP) model and then solved by a general-purpose solver. In the existing software for DIDP, a model is defined using expressions composed of a predefined set of operations. In this paper, we propose the Rust Programmable Interface for DIDP (RPID), new software for DIDP, where a model is defined by Rust functions. We discuss the design of RPID and compare it with existing DP-based frameworks, including decision diagram-based (DD-based) solvers. In our experiments, RPID is up to hundreds of times faster than the existing DIDP implementation with the same models. In addition, new DIDP models, enabled by the flexibility of RPID, outperform existing models in multiple problem classes. We also show that the relative performance of RPID and existing DD-based solvers depends on problem class with, so far, no clear dominant solver technology.
Cite as

Ryo Kuroiwa and J. Christopher Beck. RPID: Rust Programmable Interface for Domain-Independent Dynamic Programming. In 31st International Conference on Principles and Practice of Constraint Programming (CP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 340, pp. 23:1-23:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kuroiwa_et_al:LIPIcs.CP.2025.23,
  author =	{Kuroiwa, Ryo and Beck, J. Christopher},
  title =	{{RPID: Rust Programmable Interface for Domain-Independent Dynamic Programming}},
  booktitle =	{31st International Conference on Principles and Practice of Constraint Programming (CP 2025)},
  pages =	{23:1--23:21},
  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.23},
  URN =		{urn:nbn:de:0030-drops-238845},
  doi =		{10.4230/LIPIcs.CP.2025.23},
  annote =	{Keywords: Decision Diagrams \& Dynamic Programming, Modelling \& Modelling Languages}
}
Document
DOI: 10.4230/LIPIcs.CP.2025.30
Exact Methods for the Travelling Salesperson Problem with Self-Deleting Graphs

Authors: Daniel Pekar and J. Christopher Beck

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

Abstract
Finding the minimal-cost closed loop on a weighted graph where every vertex is visited exactly once is known as the Travelling Salesperson Problem (TSP). In a recently proposed variant, TSP with Self-Deleting graphs (TSP-SD), visiting a vertex i deletes a set of edges in the graph, preventing their subsequent traversal. Due to the dependency between vertex visits and edge deletion, in TSP-SD the feasibility of a cycle depends on the start node. The best performing solution approaches in the literature rely on a simple problem reformulation to find a backward tour where vertex visits add edges rather than delete them. This paper investigates exact model-based approaches, specifically Constraint Programming (CP), Domain-Independent Dynamic Programming (DIDP), and Mixed Integer Linear Programming (MIP) to solve TSP-SD. We show that simple preprocessing can substantially reduce the options for start/end vertex pairs but typically has a limited positive impact on search performance. Our numerical results demonstrate that the difference between the deletion and addition variants is small for CP and MIP but that the reformulation is critical for DIDP performance. Overall, the DIDP addition model is the best of the exact methods on all test instances and outperforms existing heuristic solvers for small and medium-sized instances while trailing in terms of solution quality on larger instances.
Cite as

Daniel Pekar and J. Christopher Beck. Exact Methods for the Travelling Salesperson Problem with Self-Deleting Graphs. In 31st International Conference on Principles and Practice of Constraint Programming (CP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 340, pp. 30:1-30:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pekar_et_al:LIPIcs.CP.2025.30,
  author =	{Pekar, Daniel and Beck, J. Christopher},
  title =	{{Exact Methods for the Travelling Salesperson Problem with Self-Deleting Graphs}},
  booktitle =	{31st International Conference on Principles and Practice of Constraint Programming (CP 2025)},
  pages =	{30:1--30:19},
  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.30},
  URN =		{urn:nbn:de:0030-drops-238914},
  doi =		{10.4230/LIPIcs.CP.2025.30},
  annote =	{Keywords: Decision Diagrams \& Dynamic Programming, Operations Research \& Mathematical Optimization, Modelling \& Modelling Languages}
}
Document
DOI: 10.4230/LIPIcs.CP.2024.12
Using Constraint Programming for Disjunctive Scheduling in Temporal AI Planning

Authors: Adam Francis Green, J. Christopher Beck, and Amanda Coles

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

Abstract
We present a novel scheduling model that leverages Constraint Programming (CP) to enhance problem solving performance in Temporal Planning. Building on the established strategy of decomposing causal and temporal reasoning, our approach abstracts two common fact structures present in many Temporal Planning problems - Semaphores and Envelopes - and performs temporal reasoning in a CP-based scheduler. At each search node in a heuristic search for a temporal plan, we construct and solve a Constraint Satisfaction Problem (CSP) and integrate feedback from the CP-based scheduler to guide the causal planning search towards a solution. Through experimental analysis, we validate the impact of these advances, demonstrating a significant reduction in both the number of states searched and in search time alongside an increase in problem-solving coverage.
Cite as

Adam Francis Green, J. Christopher Beck, and Amanda Coles. Using Constraint Programming for Disjunctive Scheduling in Temporal AI Planning. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{francisgreen_et_al:LIPIcs.CP.2024.12,
  author =	{Francis Green, Adam and Beck, J. Christopher and Coles, Amanda},
  title =	{{Using Constraint Programming for Disjunctive Scheduling in Temporal AI Planning}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{12:1--12:17},
  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.12},
  URN =		{urn:nbn:de:0030-drops-206974},
  doi =		{10.4230/LIPIcs.CP.2024.12},
  annote =	{Keywords: AI Planning, Temporal-Numeric Planning, Constraint Programming, Scheduling}
}
Document
DOI: 10.4230/LIPIcs.CP.2024.32
Solving LBBD Master Problems with Constraint Programming and Domain-Independent Dynamic Programming

Authors: Jiachen Zhang and J. Christopher Beck

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

Abstract
We investigate using Constraint Programming (CP) and Domain-Independent Dynamic Programming (DIDP) to solve the master problem in Logic-based Benders Decomposition (LBBD) models, in particular addressing the challenge of feasibility cut formulation. For CP, we exploit key variable manipulation, constraint-based expressions, and global constraints to construct three combinatorial cut encodings. For the state-based DIDP model, we propose two cut encoding approaches: using additional preconditions of state transitions or adding state constraints. Each of these approaches can be modeled using integer numeric variables or set variables, resulting in four novel encodings. We apply the three CP variants and four DIDP variants to simple assembly line balancing problems with sequence-dependent setup times type-1 (SUALBP-1). Experimental results show all approaches outperform a mixed-integer programming (MIP) based master problem and the state-of-the-art monolithic MIP model, with the three CP variants being superior to all of the DIDP approaches.
Cite as

Jiachen Zhang and J. Christopher Beck. Solving LBBD Master Problems with Constraint Programming and Domain-Independent Dynamic Programming. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 32:1-32:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{zhang_et_al:LIPIcs.CP.2024.32,
  author =	{Zhang, Jiachen and Beck, J. Christopher},
  title =	{{Solving LBBD Master Problems with Constraint Programming and Domain-Independent Dynamic Programming}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{32:1--32:21},
  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.32},
  URN =		{urn:nbn:de:0030-drops-207171},
  doi =		{10.4230/LIPIcs.CP.2024.32},
  annote =	{Keywords: constraint programming, domain-independent dynamic programming, logic-based Benders decomposition, assembly line balancing, sequence-dependent setup}
}
Document
DOI: 10.4230/LIPIcs.CP.2023.17
Optimization Models for Pickup-And-Delivery Problems with Reconfigurable Capacities

Authors: Arnoosh Golestanian, Giovanni Lo Bianco, Chengyu Tao, and J. Christopher Beck

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

Abstract
When a transportation service accommodates both people and goods, operators sometimes opt for vehicles that can be dynamically reconfigured for different demands. Motivated by air service in remote communities in Canada’s north, we define a pickup-and-delivery problem in which aircraft can add or remove seats during a multi-stop trip to accommodate varying demands. Given the demand for people and cargo as well as a seat inventory at each location, the problem consists in finding a tour that picks up and delivers all demand while potentially reconfiguring the vehicle capacity at each location by adding or removing seats. We develop a total of six models using three different approaches: constraint programming, mixed integer programming, and domain-independent dynamic programming. Our numerical experiments indicate that domain-independent dynamic programming is able to substantially outperform the other technologies on both solution quality and run-time on a set of randomly generated instances spanning the size of real problems in northern Canada.
Cite as

Arnoosh Golestanian, Giovanni Lo Bianco, Chengyu Tao, and J. Christopher Beck. Optimization Models for Pickup-And-Delivery Problems with Reconfigurable Capacities. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{golestanian_et_al:LIPIcs.CP.2023.17,
  author =	{Golestanian, Arnoosh and Bianco, Giovanni Lo and Tao, Chengyu and Beck, J. Christopher},
  title =	{{Optimization Models for Pickup-And-Delivery Problems with Reconfigurable Capacities}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{17:1--17: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.17},
  URN =		{urn:nbn:de:0030-drops-190542},
  doi =		{10.4230/LIPIcs.CP.2023.17},
  annote =	{Keywords: Pickup and delivery, Dial-a-ride problem, Optimization}
}
Document
DOI: 10.4230/LIPIcs.CP.2023.23
Large Neighborhood Beam Search for Domain-Independent Dynamic Programming

Authors: Ryo Kuroiwa and J. Christopher Beck

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

Abstract
Large neighborhood search (LNS) is an algorithmic framework that removes a part of a solution and performs search in the induced search space to find a better solution. While LNS shows strong performance in constraint programming, little work has combined LNS with state space search. We propose large neighborhood beam search (LNBS), a combination of LNS and state space search. Given a solution path, LNBS removes a partial path between two states and then performs beam search to find a better partial path. We apply LNBS to domain-independent dynamic programming (DIDP), a recently proposed generic framework for combinatorial optimization based on dynamic programming. We empirically show that LNBS finds better quality solutions than a state-of-the-art DIDP solver in five out of nine benchmark problem types with a total of 8570 problem instances. In particular, LNBS shows a significant improvement over the existing state-of-the-art DIDP solver in routing and scheduling problems.
Cite as

Ryo Kuroiwa and J. Christopher Beck. Large Neighborhood Beam Search for Domain-Independent Dynamic Programming. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kuroiwa_et_al:LIPIcs.CP.2023.23,
  author =	{Kuroiwa, Ryo and Beck, J. Christopher},
  title =	{{Large Neighborhood Beam Search for Domain-Independent Dynamic Programming}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{23:1--23:22},
  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.23},
  URN =		{urn:nbn:de:0030-drops-190605},
  doi =		{10.4230/LIPIcs.CP.2023.23},
  annote =	{Keywords: Large Neighborhood Search, Dynamic Programming, State Space Search, Combinatorial Optimization}
}
Document
DOI: 10.4230/LIPIcs.CP.2021.35
Counterfactual Explanations via Inverse Constraint Programming

Authors: Anton Korikov and J. Christopher Beck

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

Abstract
It is increasingly recognized that automated decision making systems cannot be black boxes: users require insight into the reasons that decisions are made. Explainable AI (XAI) has developed a number of approaches to this challenge, including the framework of counterfactual explanations where an explanation takes the form of the minimal change to the world required for a user’s desired decisions to be made. Building on recent work, we show that for a user query specifying an assignment to a subset of variables, a counterfactual explanation can be found using inverse optimization. Thus, we develop inverse constraint programming (CP): to our knowledge, the first definition and treatment of inverse optimization in constraint programming. We modify a cutting plane algorithm for inverse mixed-integer programming (MIP), resulting in both pure and hybrid inverse CP algorithms. We evaluate the performance of these algorithms in generating counterfactual explanations for two combinatorial optimization problems: the 0-1 knapsack problem and single machine scheduling with release dates. Our numerical experiments show that a MIP-CP hybrid approach extended with a novel early stopping criteria can substantially out-perform a MIP approach particularly when CP is the state of the art for the underlying optimization problem.
Cite as

Anton Korikov and J. Christopher Beck. Counterfactual Explanations via Inverse Constraint Programming. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{korikov_et_al:LIPIcs.CP.2021.35,
  author =	{Korikov, Anton and Beck, J. Christopher},
  title =	{{Counterfactual Explanations via Inverse Constraint Programming}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{35:1--35: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.35},
  URN =		{urn:nbn:de:0030-drops-153261},
  doi =		{10.4230/LIPIcs.CP.2021.35},
  annote =	{Keywords: Explanation, Inverse Optimization, Scheduling}
}
Document
DOI: 10.4230/DagRep.8.2.26
Planning and Operations Research (Dagstuhl Seminar 18071)

Authors: J. Christopher Beck, Daniele Magazzeni, Gabriele Röger, and Willem-Jan Van Hoeve

Published in: Dagstuhl Reports, Volume 8, Issue 2 (2018)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 18071 "Planning and Operations Research". The seminar brought together researchers in the areas of Artificial Intelligence (AI) Planning, Constraint Programming, and Operations Research. All three areas have in common that they deal with complex systems where a huge space of interacting options makes it almost impossible to humans to take optimal or even good decisions. From a historical perspective, operations research stems from the application of mathematical methods to (mostly) industrial applications while planning and constraint programming emerged as subfields of artificial intelligence where the emphasis was traditionally more on symbolic and logical search techniques for the intelligent selection and sequencing of actions to achieve a set of goals. Therefore operations research often focuses on the allocation of scarce resources such as transportation capacity, machine availability, production materials, or money, while planning focuses on the right choice of actions from a large space of possibilities. While this difference results in problems in different complexity classes, it is often possible to cast the same problem as an OR, CP, or planning problem. In this seminar, we investigated the commonalities and the overlap between the different areas to learn from each other's expertise, bring the communities closer together, and transfer knowledge about solution techniques that can be applied in all areas.
Cite as

J. Christopher Beck, Daniele Magazzeni, Gabriele Röger, and Willem-Jan Van Hoeve. Planning and Operations Research (Dagstuhl Seminar 18071). In Dagstuhl Reports, Volume 8, Issue 2, pp. 26-63, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{beck_et_al:DagRep.8.2.26,
  author =	{Beck, J. Christopher and Magazzeni, Daniele and R\"{o}ger, Gabriele and Van Hoeve, Willem-Jan},
  title =	{{Planning and Operations Research (Dagstuhl Seminar 18071)}},
  pages =	{26--63},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2018},
  volume =	{8},
  number =	{2},
  editor =	{Beck, J. Christopher and Magazzeni, Daniele and R\"{o}ger, Gabriele and Van Hoeve, Willem-Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.8.2.26},
  URN =		{urn:nbn:de:0030-drops-92894},
  doi =		{10.4230/DagRep.8.2.26},
  annote =	{Keywords: Artificial Intelligence, Automated Planning and Scheduling, Constraint Programming, Dynamic Programming, Heuristic Search, Mixed Integer Programming, Operations Research, Optimization, Real-world Applications, Reasoning under Uncertainty}
}
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