Search Results

Documents authored by Tack, Guido

Document
DOI: 10.4230/LIPIcs.CP.2023.37
Addressing Problem Drift in UNHCR Fund Allocation

Authors: Sameela Suharshani Wijesundara, Maria Garcia de la Banda, and Guido Tack

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

Abstract
Optimisation models are concise mathematical representations of real-world problems, usually developed by modelling experts in consultation with domain experts. Typically, domain experts are only indirectly involved in the problem modelling process, providing information and feedback, and thus perceive the deployed model as a black box. Unfortunately, real-world problems "drift" over time, where changes in the input data parameters and/or requirements cause the developed model to fail. This requires modelling experts to revisit and update deployed models. This paper identifies the issue of problem drift in optimisation problems using as case study a model we developed for the United Nations High Commissioner for Refugees (UNHCR) to help them allocate funds to different crises. We describe the initial model and the challenges due to problem drift that occurred over the following years. We then use this case study to explore techniques for mitigating problem drift by including domain experts in the modelling process via techniques such as domain specific languages.
Cite as

Sameela Suharshani Wijesundara, Maria Garcia de la Banda, and Guido Tack. Addressing Problem Drift in UNHCR Fund Allocation. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 37:1-37:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{wijesundara_et_al:LIPIcs.CP.2023.37,
  author =	{Wijesundara, Sameela Suharshani and Garcia de la Banda, Maria and Tack, Guido},
  title =	{{Addressing Problem Drift in UNHCR Fund Allocation}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{37:1--37:18},
  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.37},
  URN =		{urn:nbn:de:0030-drops-190740},
  doi =		{10.4230/LIPIcs.CP.2023.37},
  annote =	{Keywords: Fund Allocation, Problem Drift, Domain Specific Languages, MiniZinc}
}
Document
DOI: 10.4230/LIPIcs.CP.2022.21
Explaining Propagation for Gini and Spread with Variable Mean

Authors: Alexander Ek, Andreas Schutt, Peter J. Stuckey, and Guido Tack

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

Abstract
In optimisation problems involving multiple agents (stakeholders) we often want to make sure that the solution is balanced and fair. That is, we want to maximise total utility subject to an upper bound on the statistical dispersion (e.g., spread or the Gini coefficient) of the utility given to different agents, or minimise dispersion subject to some lower bounds on utility. These needs arise in, for example, balancing tardiness in scheduling, unwanted shifts in rostering, and desired resources in resource allocation, or minimising deviation from a baseline in schedule repair, to name a few. These problems are often quite challenging. To solve them efficiently we want to effectively reason about dispersion. Previous work has studied the case where the mean is fixed, but this may not be possible for many problems, e.g., scheduling where total utility depends on the final schedule. In this paper we introduce two log-linear-time dispersion propagators - (a) spread (variance, and indirectly standard deviation) and (b) the Gini coefficient - capable of explaining their propagations, thus allowing effective clause learning solvers to be applied to these problems. Propagators for (a) exist in the literature but do not explain themselves, while propagators for (b) have not been previously studied. We avoid introducing floating-point variables, which are usually not supported by learning solvers, by reasoning about scaled, integer versions of the constraints. We show through experimentation that clause learning can substantially improve the solving of problems where we want to bound dispersion and optimise total utility and vice versa.
Cite as

Alexander Ek, Andreas Schutt, Peter J. Stuckey, and Guido Tack. Explaining Propagation for Gini and Spread with Variable Mean. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ek_et_al:LIPIcs.CP.2022.21,
  author =	{Ek, Alexander and Schutt, Andreas and Stuckey, Peter J. and Tack, Guido},
  title =	{{Explaining Propagation for Gini and Spread with Variable Mean}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{21:1--21:16},
  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.21},
  URN =		{urn:nbn:de:0030-drops-166503},
  doi =		{10.4230/LIPIcs.CP.2022.21},
  annote =	{Keywords: Spread constraint, Gini index, Filtering algorithm, Constraint programming, Lazy clause generation}
}
Document
DOI: 10.4230/LIPIcs.CP.2021.11
Vehicle Dynamics in Pickup-And-Delivery Problems Using Electric Vehicles

Authors: Saman Ahmadi, Guido Tack, Daniel Harabor, and Philip Kilby

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

Abstract
Electric Vehicles (EVs) are set to replace vehicles based on internal combustion engines. Path planning and vehicle routing for EVs need to take their specific characteristics into account, such as reduced range, long charging times, and energy recuperation. This paper investigates the importance of vehicle dynamics parameters in energy models for EV routing, particularly in the Pickup-and-Delivery Problem (PDP). We use Constraint Programming (CP) technology to develop a complete PDP model with different charger technologies. We adapt realistic instances that consider vehicle dynamics parameters such as vehicle mass, road gradient and driving speed to varying degrees. The results of our experiments show that neglecting such fundamental vehicle dynamics parameters can affect the feasibility of planned routes for EVs, and fewer/shorter charging visits will be planned if we use energy-efficient paths instead of conventional shortest paths in the underlying system model.
Cite as

Saman Ahmadi, Guido Tack, Daniel Harabor, and Philip Kilby. Vehicle Dynamics in Pickup-And-Delivery Problems Using Electric Vehicles. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ahmadi_et_al:LIPIcs.CP.2021.11,
  author =	{Ahmadi, Saman and Tack, Guido and Harabor, Daniel and Kilby, Philip},
  title =	{{Vehicle Dynamics in Pickup-And-Delivery Problems Using Electric Vehicles}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{11:1--11:17},
  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.11},
  URN =		{urn:nbn:de:0030-drops-153020},
  doi =		{10.4230/LIPIcs.CP.2021.11},
  annote =	{Keywords: Electric vehicle routing, pickup-and-delivery problem, vehicle dynamics}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.3
Bi-Objective Search with Bi-Directional A*

Authors: Saman Ahmadi, Guido Tack, Daniel Harabor, and Philip Kilby

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
Bi-objective search is a well-known algorithmic problem, concerned with finding a set of optimal solutions in a two-dimensional domain. This problem has a wide variety of applications such as planning in transport systems or optimal control in energy systems. Recently, bi-objective A*-based search (BOA*) has shown state-of-the-art performance in large networks. This paper develops a bi-directional and parallel variant of BOA*, enriched with several speed-up heuristics. Our experimental results on 1,000 benchmark cases show that our bi-directional A* algorithm for bi-objective search (BOBA*) can optimally solve all of the benchmark cases within the time limit, outperforming the state of the art BOA*, bi-objective Dijkstra and bi-directional bi-objective Dijkstra by an average runtime improvement of a factor of five over all of the benchmark instances.
Cite as

Saman Ahmadi, Guido Tack, Daniel Harabor, and Philip Kilby. Bi-Objective Search with Bi-Directional A*. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ahmadi_et_al:LIPIcs.ESA.2021.3,
  author =	{Ahmadi, Saman and Tack, Guido and Harabor, Daniel and Kilby, Philip},
  title =	{{Bi-Objective Search with Bi-Directional A*}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{3:1--3:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.3},
  URN =		{urn:nbn:de:0030-drops-145849},
  doi =		{10.4230/LIPIcs.ESA.2021.3},
  annote =	{Keywords: Bi-objective search, heuristic search, shortest path problem}
}
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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact