5 Search Results for "Walsh, Toby"


Document
Invited Talk
Beyond Optimal Solutions for Real-World Problems (Invited Talk)

Authors: Maria Garcia de la Banda

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


Abstract
Combinatorial optimisation technology has come a long way. We now have mature high-level modelling languages in which to specify a model of the particular problem of interest [Nethercote et al., 2007; Frisch et al., 2008; Van Hentenryck, 1999; Fourer et al., 1990]; robust complete solvers in each major constraint paradigm, including Constraint Programming (CP), MaxSAT [Jessica Davies and Fahiem Bacchus, 2011; Alexey Ignatiev et al., 2019], and Mixed Integer Programming (MIP); effective incomplete search techniques that can easily be combined with complete solvers to speed up the search such as Large Neighbourhood Search [Paul Shaw, 1998]; and enough general knowledge about modelling techniques to understand the need for our models to incorporate components such as global constraints [Willem-Jan van Hoeve and Irit Katriel, 2006], symmetry constraints [Ian P. Gent et al., 2006], and more. All this has significantly reduced the amount of knowledge required to apply this technology successfully to the many different combinatorial optimisation problems that permeate our society. And yet, not many organisations use such advanced optimisation technology; instead, they often rely on the solutions provided by problem-specific algorithms that are implemented in traditional imperative languages and lack any of the above advances. Further, while advanced optimisation technology is particularly suitable for the kind of complex human-in-the-loop decision-making problems that occur in critical sectors of our society, including health, transport, energy, disaster management, environment and finance, these decisions are often still made by people with little or no technological support. In this extended abstract I argue that to change this state of affairs, our research focus needs to change from improving the technology on its own, to improving it so that users can better trust, use, and maintain the optimisation systems that we develop with it. The rest of this extended abstract discusses my personal experiences and opinion on these three points. Trust I highlight trust (which focuses on the user’s point of view) rather than trustworthiness (which is a characteristic of the software itself) because I think it is the former rather than the latter that is at stake for the adoption of optimisation technology. One of the biggest hurdles I have found for trust in the context of optimisation systems is for the domain experts to (feel like they) understand the underlying model. While many users will never do (or have to), I believe it is key for domain experts to have a high-level understanding of the constraints in the model, since their (dis)trust will likely spread through the organisation, impacting the adoption of the system. Thanks to the use of high-level modelling languages in CP, our group has achieved this [Matthias Klapperstueck et al., 2023] by documenting the constraints in a language the user knows (mathematics) and linking each constraint to the particular part of the model that implements it (via comments). While domain experts do not completely understand the model, the similarity between the format they understand (mathematics) and the model constraint has helped them verify our perception of their problem and improved their trust in the model. However, more needs to be done in this direction via the development of formal techniques. For example, our group is exploring the use of domain-specific languages [Hudak, 1997] as a bridge between domain experts and modellers that helps both trust and maintenance (see later). This [Sameela Suharshani Wijesundara et al., 2023] and other approaches need to be explored. A very significant source of trust for our domain experts (and of trustworthiness for the software) has been the development of two different models implemented by two different people for the same problem [Matthias Klapperstueck et al., 2023]. While this can be seen as a prohibitively expensive exercise, it did not take that long once the first model was mature, is a good way to onboard new optimisation team members, and has helped up detect not only bugs but also differences in the interpretation of domain expert information. For optimisation problems where it is not possible to verify the optimality (or even correctness) of the solution, we see such redundant modelling as the only solution for now. Interestingly, a significant step forward in obtaining the trust of our domain experts has been the generation of an optimality gap whenever an optimal solution could not be found due to time constraints. While explaining this concept took time, once understood it has boosted their trust, particularly when tackling problems where the solution is not easy verifiable or when approximated models/data are used (needed for speed, see later). This makes it difficult to work with CP and SAT solvers, as they usually lack tight lower bounds. Finally, trust is often developed through the use of the system, which I discuss below. Use Usability is known to be key for the deployment of software systems. By "system" in our context, I refer to the combination of the problem model(s), the associated solver(s) and, importantly, the User Interface (UI) that often integrates them and is fundamental to their success. In addition to the traditional usability characteristics of software systems, I believe an optimisation system requires particular care in the following areas. Interaction, i.e., the system must allow users to interact with the UI not only to provide and modify the input data, but also to modify the constraints (at the very least by turning some on/off) as well as explore and compare solutions, as argued in [David Meignan et al., 2015; Jie Liu et al., 2021]. Incremental compilers and solvers would significantly help in making this easier, as well as generic ways for the UIs to communicate with them. Conflict resolution, that is, ensuring the system can not only detect infeasible instances, but also support users in understanding the data/constraints that cause infeasibility and how to modify the instance to make it feasible. Any interactive optimisation system that has users, will likely have conflicts. Thus, it is mandatory for CP to improve its conflict resolution technology which, while existent [João Marques-Silva and Alessandro Previti, 2014; Lauffer and Topcu, 2019; Ilankaikone Senthooran et al., 2023], is not widespread and it is often still problem-dependent, overwhelming (in the number of constraints shown to the user) and slow. Without it, users will be "stumped" when (rather than if) infeasibility is reached. Solution diversity, that is, supporting users in obtaining a diverse set of (close-to-optimal) solutions, where diversity is measured by a user-provided metric modelled somehow. While some solver-independent technology has been developed and implemented for this [Emmanuel Hebrard et al., 2005; Thierry Petit and Andrew C. Trapp, 2015; Linnea Ingmar et al., 2020], it should be easier to use and more widespread. Further, it requires sophisticated solution comparison capabilities and, importantly, for optimal solutions to be found in seconds rather than hours. This brings me to speed, an area where CP solvers are falling behind. Most of our research group applications now use MIP solvers due to the need for floats (which precludes us from using learning solvers such as Chuffed [Geoffrey Chu, 2013]), but also to the lack of effective warm-start processes that are available in MIP solvers. Interestingly, data and model approximations have been proved to achieve orders of magnitude speedups with small reductions in optimality [Matthias Klapperstueck et al., 2023]. Developing generic (i.e., problem independent) accurate approximations would be extremely useful for complex decision systems. Other areas where I think generic CP methods are worth investigating more include dealing with uncertainty and online problems, ensuring solution fairness (even if it is over time), and studying predict + optimise approaches. Maintain I know very few papers devoted to the issue of maintenance in optimisation technology. While this may be due to my lack of knowledge, I suspect it is also due to the limited adoption of optimisation technology. While the issues in this area are again common to other software systems, I believe the solutions for CP require special attention. For example, the issue of changes in user requirements (that our research group calls problem drift) seems particularly prevalent in decision-making systems, as such problems can evolve rapidly due to unforeseen circumstances. This can make optimisation systems obsolete faster than expected. Our research group has proposed to tackle problem drift by developing a requirements model implemented in the above-mentioned MDSLs and created by both domain experts and modellers that, when modified re-generates parts of the model to support the modifications [Sameela Suharshani Wijesundara et al., 2023]. This and other approaches such as the creation of reusable models components [Sophia Saller and Jana Koehler, 2022; Toby Walsh, 2003], or instantiatable classes for common problem domains, are worth investigating.

Cite as

Maria Garcia de la Banda. Beyond Optimal Solutions for Real-World Problems (Invited Talk). In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 1:1-1:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{garciadelabanda:LIPIcs.CP.2023.1,
  author =	{Garcia de la Banda, Maria},
  title =	{{Beyond Optimal Solutions for Real-World Problems}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{1:1--1:4},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.1},
  URN =		{urn:nbn:de:0030-drops-190384},
  doi =		{10.4230/LIPIcs.CP.2023.1},
  annote =	{Keywords: Combinatorial optimisation systems, usability, trust, maintenance}
}
Document
Voting: Beyond Simple Majorities and Single-Winner Elections (Dagstuhl Seminar 17261)

Authors: Dorothea Baumeister, Piotr Faliszewski, Annick Laruelle, and Toby Walsh

Published in: Dagstuhl Reports, Volume 7, Issue 6 (2018)


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 17261 "Voting: Beyond simple majorities and single-winner elections". The seminar featured five survey talks, a series of classic scientific presentations, working group discussions, open problems sessions (with the first one used to establish working groups and the last one to present their results). The seminar was mostly focused on multiwinner elections (from discussions of their algorithmic properties to political-science considerations), but the topics of real-life voting experiments and strategic behavior received attention as well.

Cite as

Dorothea Baumeister, Piotr Faliszewski, Annick Laruelle, and Toby Walsh. Voting: Beyond Simple Majorities and Single-Winner Elections (Dagstuhl Seminar 17261). In Dagstuhl Reports, Volume 7, Issue 6, pp. 109-134, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@Article{baumeister_et_al:DagRep.7.6.109,
  author =	{Baumeister, Dorothea and Faliszewski, Piotr and Laruelle, Annick and Walsh, Toby},
  title =	{{Voting: Beyond Simple Majorities and Single-Winner Elections (Dagstuhl Seminar 17261)}},
  pages =	{109--134},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{7},
  number =	{6},
  editor =	{Baumeister, Dorothea and Faliszewski, Piotr and Laruelle, Annick and Walsh, Toby},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.7.6.109},
  URN =		{urn:nbn:de:0030-drops-82882},
  doi =		{10.4230/DagRep.7.6.109},
  annote =	{Keywords: artificial intelligence, collective decision making, computational social choice, multi agent systems, preference aggregation, preference elicitation}
}
Document
Answer Set Solving with Lazy Nogood Generation

Authors: Christian Drescher and Toby Walsh

Published in: LIPIcs, Volume 17, Technical Communications of the 28th International Conference on Logic Programming (ICLP'12) (2012)


Abstract
Although Answer Set Programming (ASP) systems are highly optimised, their performance is sensitive to the size of the input and the inference it encodes. We address this deficiency by introducing a new extension to ASP solving. The idea is to integrate external propagators to represent parts of the encoding implicitly, rather than generating it a-priori. To match the state-of-the-art in conflict-driven solving, however, external propagators can make their inference explicit on demand. We demonstrate applicability in a novel Constraint Answer Set Programming system that can seamlessly integrate constraint propagation without sacrifficing the advantages of conflict-driven techniques. Experiments provide evidence for computational impact.

Cite as

Christian Drescher and Toby Walsh. Answer Set Solving with Lazy Nogood Generation. In Technical Communications of the 28th International Conference on Logic Programming (ICLP'12). Leibniz International Proceedings in Informatics (LIPIcs), Volume 17, pp. 188-200, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)


Copy BibTex To Clipboard

@InProceedings{drescher_et_al:LIPIcs.ICLP.2012.188,
  author =	{Drescher, Christian and Walsh, Toby},
  title =	{{Answer Set Solving with Lazy Nogood Generation}},
  booktitle =	{Technical Communications of the 28th International Conference on Logic Programming (ICLP'12)},
  pages =	{188--200},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-43-9},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{17},
  editor =	{Dovier, Agostino and Santos Costa, V{\'\i}tor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICLP.2012.188},
  URN =		{urn:nbn:de:0030-drops-36216},
  doi =		{10.4230/LIPIcs.ICLP.2012.188},
  annote =	{Keywords: Conflict-Driven Nogood Learning, Constraint Answer Set Programming, Constraint Propagation, Lazy Nogood Generation}
}
Document
Modelling Grammar Constraints with Answer Set Programming

Authors: Christian Drescher and Toby Walsh

Published in: LIPIcs, Volume 11, Technical Communications of the 27th International Conference on Logic Programming (ICLP'11) (2011)


Abstract
Representing and solving constraint satisfaction problems is one of the challenges of artificial intelligence. In this paper, we present answer set programming (ASP) models for an important and very general class of constraints, including all constraints specified via grammars or automata that recognise some formal language. We argue that our techniques are effective and efficient, e.g., unit-propagation of an ASP solver can achieve domain consistency on the original constraint. Experiments demonstrate computational impact.

Cite as

Christian Drescher and Toby Walsh. Modelling Grammar Constraints with Answer Set Programming. In Technical Communications of the 27th International Conference on Logic Programming (ICLP'11). Leibniz International Proceedings in Informatics (LIPIcs), Volume 11, pp. 28-39, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{drescher_et_al:LIPIcs.ICLP.2011.28,
  author =	{Drescher, Christian and Walsh, Toby},
  title =	{{Modelling Grammar Constraints with Answer Set Programming}},
  booktitle =	{Technical Communications of the 27th International Conference on Logic Programming (ICLP'11)},
  pages =	{28--39},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-31-6},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{11},
  editor =	{Gallagher, John P. and Gelfond, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICLP.2011.28},
  URN =		{urn:nbn:de:0030-drops-31723},
  doi =		{10.4230/LIPIcs.ICLP.2011.28},
  annote =	{Keywords: answer set programming, grammar-, regular-, precedence constraint}
}
Document
Manipulability of Single Transferable Vote

Authors: Toby Walsh

Published in: Dagstuhl Seminar Proceedings, Volume 10101, Computational Foundations of Social Choice (2010)


Abstract
For many voting rules, it is NP-hard to compute a successful manipulation. However, NP-hardness only bounds the worst-case complexity. Recent theoretical results suggest that manipulation may often be easy in practice. We study empirically the cost of manipulating the single transferable vote (STV) rule. This was one of the first rules shown to be NP-hard to manipulate. It also appears to be one of the harder rules to manipulate since it involves multiple rounds and since, unlike many other rules, it is NP-hard for a single agent to manipulate without weights on the votes or uncertainty about how the other agents have voted. In almost every election in our experiments, it was easy to compute how a single agent could manipulate the election or to prove that manipulation by a single agent was impossible. It remains an interesting open question if manipulation by a coalition of agents is hard to compute in practice.

Cite as

Toby Walsh. Manipulability of Single Transferable Vote. In Computational Foundations of Social Choice. Dagstuhl Seminar Proceedings, Volume 10101, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{walsh:DagSemProc.10101.4,
  author =	{Walsh, Toby},
  title =	{{Manipulability of Single Transferable Vote}},
  booktitle =	{Computational Foundations of Social Choice},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10101},
  editor =	{Felix Brandt and Vincent Conitzer and Lane A. Hemaspaandra and Jean-Francois Laslier and William S. Zwicker},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10101.4},
  URN =		{urn:nbn:de:0030-drops-25585},
  doi =		{10.4230/DagSemProc.10101.4},
  annote =	{Keywords: Computational social choice, manipulability, STV voting, NP-hardness}
}
  • Refine by Author
  • 4 Walsh, Toby
  • 2 Drescher, Christian
  • 1 Baumeister, Dorothea
  • 1 Faliszewski, Piotr
  • 1 Garcia de la Banda, Maria
  • Show More...

  • Refine by Classification
  • 1 Human-centered computing → Information visualization
  • 1 Theory of computation → Constraint and logic programming
  • 1 Theory of computation → Integer programming

  • Refine by Keyword
  • 1 Combinatorial optimisation systems
  • 1 Computational social choice
  • 1 Conflict-Driven Nogood Learning
  • 1 Constraint Answer Set Programming
  • 1 Constraint Propagation
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 1 2010
  • 1 2011
  • 1 2012
  • 1 2017
  • 1 2023

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