16 Search Results for "Marques-Silva, Joao"

Volume

OASIcs, Volume 102

Third International Computer Programming Education Conference (ICPEC 2022)

ICPEC 2022, June 2-3, 2022, Polytechnic Institute of Cávado and Ave (IPCA), Barcelos, Portugal

Editors: Alberto Simões and João Carlos Silva

Document
Invited Talk
DOI: 10.4230/LIPIcs.CP.2023.1
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
DOI: 10.4230/LIPIcs.STACS.2023.21
Extending Merge Resolution to a Family of QBF-Proof Systems

Authors: Sravanthi Chede and Anil Shukla

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract
Merge Resolution (MRes [Olaf Beyersdorff et al., 2021]) is a recently introduced proof system for false QBFs. Unlike other known QBF proof systems, it builds winning strategies for the universal player (countermodels) within the proofs as merge maps. Merge maps are deterministic branching programs in which isomorphism checking is efficient, as a result MRes is a polynomial time verifiable proof system. In this paper, we introduce a family of proof systems MRes-ℛ in which the information of countermodels are stored in any pre-fixed complete representation ℛ. Hence, corresponding to each possible complete representation ℛ, we have a sound and refutationally complete QBF-proof system in MRes-ℛ. To handle these arbitrary representations, we introduce consistency checking rules in MRes-ℛ instead of the isomorphism checking in MRes. As a result these proof systems are not polynomial time verifiable (Non-P). Consequently, the paper shows that using merge maps is too restrictive and with a slight change in rules, it can be replaced with arbitrary representations leading to several interesting proof systems. We relate these new systems with the implicit proof system from the algorithm in [Joshua Blinkhorn et al., 2021], which was designed to solve DQBFs (Dependency QBFs) using clause-strategy pairs like MRes. We use the OBDD (Ordered Binary Decision Diagrams) representation suggested in [Joshua Blinkhorn et al., 2021] and deduce that "Ordered" versions of the proof systems in MRes-ℛ are indeed polynomial time verifiable. On the lower bound side, we lift the lower bound result of regular MRes ([Olaf Beyersdorff et al., 2020]) by showing that the completion principle formulas (CR_n) from [Mikolás Janota and João Marques-Silva, 2015] which are shown to be hard for regular MRes in [Olaf Beyersdorff et al., 2020], are also hard for any regular proof system in MRes-ℛ. Thereby, the paper lifts the lower bound of regular MRes to an entire class of proof systems, which use various complete representations, including those undiscovered, instead of only merge maps. Thereby proving that the hardness of CR_n formulas is intact even after changing the weak isomorphism checking in MRes to the stronger consistency checking in MRes-ℛ.
Cite as

Sravanthi Chede and Anil Shukla. Extending Merge Resolution to a Family of QBF-Proof Systems. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 21:1-21:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chede_et_al:LIPIcs.STACS.2023.21,
  author =	{Chede, Sravanthi and Shukla, Anil},
  title =	{{Extending Merge Resolution to a Family of QBF-Proof Systems}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{21:1--21:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.21},
  URN =		{urn:nbn:de:0030-drops-176737},
  doi =		{10.4230/LIPIcs.STACS.2023.21},
  annote =	{Keywords: Proof complexity, QBFs, Merge Resolution, Simulation, Lower Bound}
}
Document
Complete Volume
DOI: 10.4230/OASIcs.ICPEC.2022
OASIcs, Volume 102, ICPEC 2022, Complete Volume

Authors: Alberto Simões and João Carlos Silva

Published in: OASIcs, Volume 102, Third International Computer Programming Education Conference (ICPEC 2022)

Abstract
OASIcs, Volume 102, ICPEC 2022, Complete Volume
Cite as

Third International Computer Programming Education Conference (ICPEC 2022). Open Access Series in Informatics (OASIcs), Volume 102, pp. 1-164, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Proceedings{simoes_et_al:OASIcs.ICPEC.2022,
  title =	{{OASIcs, Volume 102, ICPEC 2022, Complete Volume}},
  booktitle =	{Third International Computer Programming Education Conference (ICPEC 2022)},
  pages =	{1--164},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-229-7},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{102},
  editor =	{Sim\~{o}es, Alberto and Silva, Jo\~{a}o Carlos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ICPEC.2022},
  URN =		{urn:nbn:de:0030-drops-166039},
  doi =		{10.4230/OASIcs.ICPEC.2022},
  annote =	{Keywords: OASIcs, Volume 102, ICPEC 2022, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/OASIcs.ICPEC.2022.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Alberto Simões and João Carlos Silva

Published in: OASIcs, Volume 102, Third International Computer Programming Education Conference (ICPEC 2022)

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

Third International Computer Programming Education Conference (ICPEC 2022). Open Access Series in Informatics (OASIcs), Volume 102, pp. 0:i-0:xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{simoes_et_al:OASIcs.ICPEC.2022.0,
  author =	{Sim\~{o}es, Alberto and Silva, Jo\~{a}o Carlos},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{Third International Computer Programming Education Conference (ICPEC 2022)},
  pages =	{0:i--0:xiv},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-229-7},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{102},
  editor =	{Sim\~{o}es, Alberto and Silva, Jo\~{a}o Carlos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ICPEC.2022.0},
  URN =		{urn:nbn:de:0030-drops-166044},
  doi =		{10.4230/OASIcs.ICPEC.2022.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/OASIcs.ICPEC.2022.1
Value-Focused Investigation into Programming Languages Affinity

Authors: Alvaro Costa Neto, Cristiana Araújo, Maria João Varanda Pereira, and Pedro Rangel Henriques

Published in: OASIcs, Volume 102, Third International Computer Programming Education Conference (ICPEC 2022)

Abstract
The search for better techniques to teach computer programming is paramount in order to improve the students' learning experiences. Several approaches have been proposed throughout the years, usually through technical solutions such as evaluation systems, digital classrooms, interactive lessons and so on. Personal factors, such as affinity, have been largely unexplored due to their qualitative and abstract nature. The results of a preliminary survey on how and why affinity is created between programmers and their favorite languages, conducted on a master’s degree class at Universidade do Minho, showed unexpected results as to which languages became favorites and the possible reasons for the students' choices. Aiming at further exploration on this topic and continuation of this research, the Value-Focused Thinking method was applied in order to construct a more complex, in-depth survey. This value-oriented method kept focus under control and even raised a handful of opportunities to improve the research as a whole. This paper describes the Value-Focused Thinking method and how it was applied to construct a new and deeper computer programming education survey to understand affinity with languages.
Cite as

Alvaro Costa Neto, Cristiana Araújo, Maria João Varanda Pereira, and Pedro Rangel Henriques. Value-Focused Investigation into Programming Languages Affinity. In Third International Computer Programming Education Conference (ICPEC 2022). Open Access Series in Informatics (OASIcs), Volume 102, pp. 1:1-1:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{costaneto_et_al:OASIcs.ICPEC.2022.1,
  author =	{Costa Neto, Alvaro and Ara\'{u}jo, Cristiana and Pereira, Maria Jo\~{a}o Varanda and Henriques, Pedro Rangel},
  title =	{{Value-Focused Investigation into Programming Languages Affinity}},
  booktitle =	{Third International Computer Programming Education Conference (ICPEC 2022)},
  pages =	{1:1--1:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-229-7},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{102},
  editor =	{Sim\~{o}es, Alberto and Silva, Jo\~{a}o Carlos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ICPEC.2022.1},
  URN =		{urn:nbn:de:0030-drops-166051},
  doi =		{10.4230/OASIcs.ICPEC.2022.1},
  annote =	{Keywords: Computer Programming, Programming Languages, Affinity, Education, Learning, Value-Focused Thinking}
}
Document
DOI: 10.4230/DagRep.11.8.1
Extending the Synergies Between SAT and Description Logics (Dagstuhl Seminar 21361)

Authors: Joao Marques-Silva, Rafael Peñaloza, and Uli Sattler

Published in: Dagstuhl Reports, Volume 11, Issue 8 (2022)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 21361 "Extending the Synergies Between SAT and Description Logics". Propositional satisfiability (SAT) and description logics (DL) are two successful areas of computational logic where automated reasoning plays a fundamental role. While they share a common core (formalised on logic), the developments in both areas have diverged in their scopes, methods, and applications. The goal of this seminar was to reconnect the SAT and DL communities (understood in a broad sense) so that they can benefit from each other. The seminar thus focused on explaining the foundational principles, main results, and open problems of each area, and discussing potential avenues for collaborative progress.
Cite as

Joao Marques-Silva, Rafael Peñaloza, and Uli Sattler. Extending the Synergies Between SAT and Description Logics (Dagstuhl Seminar 21361). In Dagstuhl Reports, Volume 11, Issue 8, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{marquessilva_et_al:DagRep.11.8.1,
  author =	{Marques-Silva, Joao and Pe\~{n}aloza, Rafael and Sattler, Uli},
  title =	{{Extending the Synergies Between SAT and Description Logics (Dagstuhl Seminar 21361)}},
  pages =	{1--10},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{11},
  number =	{8},
  editor =	{Marques-Silva, Joao and Pe\~{n}aloza, Rafael and Sattler, Uli},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.11.8.1},
  URN =		{urn:nbn:de:0030-drops-157661},
  doi =		{10.4230/DagRep.11.8.1},
  annote =	{Keywords: description logics, propositional satisfiability, reasoning services, standard and non-standard inferences}
}
Document
DOI: 10.4230/LIPIcs.CP.2021.21
On the Tractability of Explaining Decisions of Classifiers

Authors: Martin C. Cooper and João Marques-Silva

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

Abstract
Explaining decisions is at the heart of explainable AI. We investigate the computational complexity of providing a formally-correct and minimal explanation of a decision taken by a classifier. In the case of threshold (i.e. score-based) classifiers, we show that a complexity dichotomy follows from the complexity dichotomy for languages of cost functions. In particular, submodular classifiers allow tractable explanation of positive decisions, but not negative decisions (assuming P≠NP). This is an example of the possible asymmetry between the complexity of explaining positive and negative decisions of a particular classifier. Nevertheless, there are large families of classifiers for which explaining both positive and negative decisions is tractable, such as monotone or linear classifiers. We extend tractable cases to constrained classifiers (when there are constraints on the possible input vectors) and to the search for contrastive rather than abductive explanations. Indeed, we show that tractable classes coincide for abductive and contrastive explanations in the constrained or unconstrained settings.
Cite as

Martin C. Cooper and João Marques-Silva. On the Tractability of Explaining Decisions of Classifiers. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cooper_et_al:LIPIcs.CP.2021.21,
  author =	{Cooper, Martin C. and Marques-Silva, Jo\~{a}o},
  title =	{{On the Tractability of Explaining Decisions of Classifiers}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{21:1--21: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.21},
  URN =		{urn:nbn:de:0030-drops-153125},
  doi =		{10.4230/LIPIcs.CP.2021.21},
  annote =	{Keywords: machine learning, tractability, explanations, weighted constraint satisfaction}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2021.12
A Branch-Price-And-Cut Algorithm for Stochastic Crowd Shipping Last-Mile Delivery with Correlated Marginals

Authors: Marco Silva, João Pedro Pedroso, Ana Viana, and Xenia Klimentova

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)

Abstract
We study last-mile delivery with the option of crowd shipping, where a company makes use of occasional drivers to complement its vehicle’s fleet in the activity of delivering products to its customers. We model it as a data-driven distributionally robust optimization approach to the capacitated vehicle routing problem. We assume the marginals of the defined uncertainty vector are known, but the joint distribution is difficult to estimate. The presence of customers and available occasional drivers can be random. We adopt a strategic planning perspective, where an optimal a priori solution is calculated before the uncertainty is revealed. Therefore, without the need for online resolution performance, we can experiment with exact solutions. Solving the problem defined above is challenging: not only the first-stage problem is already NP-Hard, but also the uncertainty and potentially the second-stage decisions are binary of high dimension, leading to non-convex optimization formulations that are complex to solve. We propose a branch-price-and-cut algorithm taking into consideration measures that exploit the intrinsic characteristics of our problem and reduce the complexity to solve it.
Cite as

Marco Silva, João Pedro Pedroso, Ana Viana, and Xenia Klimentova. A Branch-Price-And-Cut Algorithm for Stochastic Crowd Shipping Last-Mile Delivery with Correlated Marginals. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{silva_et_al:OASIcs.ATMOS.2021.12,
  author =	{Silva, Marco and Pedroso, Jo\~{a}o Pedro and Viana, Ana and Klimentova, Xenia},
  title =	{{A Branch-Price-And-Cut Algorithm for Stochastic Crowd Shipping Last-Mile Delivery with Correlated Marginals}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{12:1--12:20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.12},
  URN =		{urn:nbn:de:0030-drops-148811},
  doi =		{10.4230/OASIcs.ATMOS.2021.12},
  annote =	{Keywords: Last-mile delivery, Stochastic Vehicle Routing Problem, Crowd shipping, Distributionally Robust Optimization, Data-driven Optimization}
}
Document
DOI: 10.4230/OASIcs.SLATE.2021.12
Semantic Search of Mobile Applications Using Word Embeddings

Authors: João Coelho, António Neto, Miguel Tavares, Carlos Coutinho, Ricardo Ribeiro, and Fernando Batista

Published in: OASIcs, Volume 94, 10th Symposium on Languages, Applications and Technologies (SLATE 2021)

Abstract
This paper proposes a set of approaches for the semantic search of mobile applications, based on their name and on the unstructured textual information contained in their description. The proposed approaches make use of word-level, character-level, and contextual word-embeddings that have been trained or fine-tuned using a dataset of about 500 thousand mobile apps, collected in the scope of this work. The proposed approaches have been evaluated using a public dataset that includes information about 43 thousand applications, and 56 manually annotated non-exact queries. Our results show that both character-level embeddings trained on our data, and fine-tuned RoBERTa models surpass the performance of the other existing retrieval strategies reported in the literature.
Cite as

João Coelho, António Neto, Miguel Tavares, Carlos Coutinho, Ricardo Ribeiro, and Fernando Batista. Semantic Search of Mobile Applications Using Word Embeddings. In 10th Symposium on Languages, Applications and Technologies (SLATE 2021). Open Access Series in Informatics (OASIcs), Volume 94, pp. 12:1-12:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{coelho_et_al:OASIcs.SLATE.2021.12,
  author =	{Coelho, Jo\~{a}o and Neto, Ant\'{o}nio and Tavares, Miguel and Coutinho, Carlos and Ribeiro, Ricardo and Batista, Fernando},
  title =	{{Semantic Search of Mobile Applications Using Word Embeddings}},
  booktitle =	{10th Symposium on Languages, Applications and Technologies (SLATE 2021)},
  pages =	{12:1--12:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-202-0},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{94},
  editor =	{Queir\'{o}s, Ricardo and Pinto, M\'{a}rio and Sim\~{o}es, Alberto and Portela, Filipe and Pereira, Maria Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SLATE.2021.12},
  URN =		{urn:nbn:de:0030-drops-144292},
  doi =		{10.4230/OASIcs.SLATE.2021.12},
  annote =	{Keywords: Semantic Search, Word Embeddings, Elasticsearch, Mobile Applications}
}
Document
DOI: 10.4230/OASIcs.SLATE.2020.4
BhTSL, Behavior Trees Specification and Processing

Authors: Miguel Oliveira, Pedro Mimoso Silva, Pedro Moura, José João Almeida, and Pedro Rangel Henriques

Published in: OASIcs, Volume 83, 9th Symposium on Languages, Applications and Technologies (SLATE 2020)

Abstract
In the context of game development, there is always the need for describing behaviors for various entities, whether NPCs or even the world itself. That need requires a formalism to describe properly such behaviors. As the gaming industry has been growing, many approaches were proposed. First, finite state machines were used and evolved to hierarchical state machines. As that formalism was not enough, a more powerful concept appeared. Instead of using states for describing behaviors, people started to use tasks. This concept was incorporated in behavior trees. This paper focuses in the specification and processing of Behavior Trees. A DSL designed for that purpose will be introduced. It will also be discussed a generator that produces LaTeX diagrams to document the trees, and a Python module to implement the behavior described. Additionally, a simulator will be presented. These achievements will be illustrated using a concrete game as a case study.
Cite as

Miguel Oliveira, Pedro Mimoso Silva, Pedro Moura, José João Almeida, and Pedro Rangel Henriques. BhTSL, Behavior Trees Specification and Processing. In 9th Symposium on Languages, Applications and Technologies (SLATE 2020). Open Access Series in Informatics (OASIcs), Volume 83, pp. 4:1-4:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{oliveira_et_al:OASIcs.SLATE.2020.4,
  author =	{Oliveira, Miguel and Silva, Pedro Mimoso and Moura, Pedro and Almeida, Jos\'{e} Jo\~{a}o and Henriques, Pedro Rangel},
  title =	{{BhTSL, Behavior Trees Specification and Processing}},
  booktitle =	{9th Symposium on Languages, Applications and Technologies (SLATE 2020)},
  pages =	{4:1--4:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-165-8},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{83},
  editor =	{Sim\~{o}es, Alberto and Henriques, Pedro Rangel and Queir\'{o}s, Ricardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SLATE.2020.4},
  URN =		{urn:nbn:de:0030-drops-130174},
  doi =		{10.4230/OASIcs.SLATE.2020.4},
  annote =	{Keywords: Game development, Behavior trees (BT), NPC, DSL, Code generation}
}
Document
DOI: 10.4230/OASIcs.SLATE.2020.5
DAOLOT: A Semantic Browser

Authors: João Bruno Silva, André Santos, and José Paulo Leal

Published in: OASIcs, Volume 83, 9th Symposium on Languages, Applications and Technologies (SLATE 2020)

Abstract
The goal of the Semantic Web is to allow the software agents around us and AIs to extract information from the Internet as easily as humans do. This semantic web is a network of connected graphs, where relations between concepts and entities make up a layout that is very easy for machines to navigate. At the moment, there are only a few tools that enable humans to navigate this new layer of the Internet, and those that exist are for the most part very specialized tools that require from the user a lot of pre-existing knowledge about the technologies behind this structure. In this article we report on the development of DAOLOT, a search engine that allows users with no previous knowledge of the semantic web to take full advantage of its information network. This paper presents its design, the algorithm behind it and the results of the validation testing conducted with users. The results of our validation testing show that DAOLOT is useful and intuitive to users, even those without any previous knowledge of the field, and provides curated information from multiple sources instantly about any topic.
Cite as

João Bruno Silva, André Santos, and José Paulo Leal. DAOLOT: A Semantic Browser. In 9th Symposium on Languages, Applications and Technologies (SLATE 2020). Open Access Series in Informatics (OASIcs), Volume 83, pp. 5:1-5:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{silva_et_al:OASIcs.SLATE.2020.5,
  author =	{Silva, Jo\~{a}o Bruno and Santos, Andr\'{e} and Leal, Jos\'{e} Paulo},
  title =	{{DAOLOT: A Semantic Browser}},
  booktitle =	{9th Symposium on Languages, Applications and Technologies (SLATE 2020)},
  pages =	{5:1--5:11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-165-8},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{83},
  editor =	{Sim\~{o}es, Alberto and Henriques, Pedro Rangel and Queir\'{o}s, Ricardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SLATE.2020.5},
  URN =		{urn:nbn:de:0030-drops-130188},
  doi =		{10.4230/OASIcs.SLATE.2020.5},
  annote =	{Keywords: Semantic, Web, Named Entities, Search, SPARQL, RDF, COMUNICA}
}
Document
DOI: 10.4230/OASIcs.SLATE.2020.6
Musikla: Language for Generating Musical Events

Authors: Pedro Miguel Oliveira da Silva and José João Almeida

Published in: OASIcs, Volume 83, 9th Symposium on Languages, Applications and Technologies (SLATE 2020)

Abstract
In this paper, we'll discuss a simple approach to integrating musical events, such as notes or chords, into a programming language. This means treating music sequences as a first class citizen. It will be possible to save those sequences into variables or play them right away, pass them into functions or apply operators on them (like transposing or repeating the sequence). Furthermore, instead of just allowing static sequences to be generated, we'll integrate a music keyboard system that easily allows the user to bind keys (or other kinds of events) to expressions. Finally, it is important to provide the user with multiple and extensible ways of outputing their music, such as synthesizing it into a file or directly into the speakers, or writing a MIDI or music sheet file. We'll structure this paper first with an analysis of the problem and its particular requirements. Then we will discuss the solution we developed to meet those requirements. Finally we'll analyze the result and discuss possible alternative routes we could've taken.
Cite as

Pedro Miguel Oliveira da Silva and José João Almeida. Musikla: Language for Generating Musical Events. In 9th Symposium on Languages, Applications and Technologies (SLATE 2020). Open Access Series in Informatics (OASIcs), Volume 83, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{dasilva_et_al:OASIcs.SLATE.2020.6,
  author =	{da Silva, Pedro Miguel Oliveira and Almeida, Jos\'{e} Jo\~{a}o},
  title =	{{Musikla: Language for Generating Musical Events}},
  booktitle =	{9th Symposium on Languages, Applications and Technologies (SLATE 2020)},
  pages =	{6:1--6:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-165-8},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{83},
  editor =	{Sim\~{o}es, Alberto and Henriques, Pedro Rangel and Queir\'{o}s, Ricardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SLATE.2020.6},
  URN =		{urn:nbn:de:0030-drops-130194},
  doi =		{10.4230/OASIcs.SLATE.2020.6},
  annote =	{Keywords: Domain Specific Language, Music Notation, Interpreter, Programming Language}
}
Document
DOI: 10.4230/LIPIcs.FUN.2021.12
A Phase Transition in Minesweeper

Authors: Ross Dempsey and Charles Guinn

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

Abstract
We study the average-case complexity of the classic Minesweeper game in which players deduce the locations of mines on a two-dimensional lattice. Playing Minesweeper is known to be co-NP-complete. We show empirically that Minesweeper exhibits a phase transition analogous to the well-studied SAT phase transition. Above the critical mine density it becomes almost impossible to play Minesweeper by logical inference. We use a reduction to Boolean unsatisfiability to characterize the hardness of Minesweeper instances, and show that the hardness peaks at the phase transition. Furthermore, we demonstrate algorithmic barriers at the phase transition for polynomial-time approaches to Minesweeper inference. Finally, we comment on expectations for the asymptotic behavior of the phase transition.
Cite as

Ross Dempsey and Charles Guinn. A Phase Transition in Minesweeper. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 12:1-12:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{dempsey_et_al:LIPIcs.FUN.2021.12,
  author =	{Dempsey, Ross and Guinn, Charles},
  title =	{{A Phase Transition in Minesweeper}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{12:1--12:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.12},
  URN =		{urn:nbn:de:0030-drops-127735},
  doi =		{10.4230/LIPIcs.FUN.2021.12},
  annote =	{Keywords: Complexity of Games, Minesweeper}
}
Document
DOI: 10.4230/OASIcs.ICPEC.2020.2
Challenges and Solutions from an Embedded Programming Bootcamp

Authors: J. Pedro Amaro, Jorge Barreiros, Fernanda Coutinho, João Durães, Frederico Santos, Ana Alves, Marco Silva, and João Cunha

Published in: OASIcs, Volume 81, First International Computer Programming Education Conference (ICPEC 2020)

Abstract
Due to the proliferation of IT companies developing web and mobile applications, computer programmers are in such high demand that universities can’t satisfy it with newly graduated students. In response, some organisations started to create coding bootcamps, providing intensive full-time courses focused on unemployed people or individuals seeking for a career change. There is, however, a different set of skills that is becoming increasingly required, but is not addressed by those courses: embedded programming. In fact, the Internet of Things is connecting every device to the internet, thus making knowledge on hardware and C/C++ programming very relevant skills. A group of computer science and electrical engineering university teachers, in collaboration with several industry stakeholders, have promoted an embedded systems programming course in C and C++. This course is based on an intensive project-based approach comprising 6 months of daylong classes followed by 9 months of paid internships. After two editions, thirty embedded programmers, with no relevant previous programming experience, have been placed with the partners’ working force. In this paper, the course organisation and pedagogical methodologies are described. Problems, challenges and adopted solutions are presented and analysed. We conclude that in spite of the intense rhythm and demanding nature of the subject matter, it is possible to find the structure and solutions that keep students engaged and motivated throughout the course, allowing them to gain the required competences and successfully transition into a new career path.
Cite as

J. Pedro Amaro, Jorge Barreiros, Fernanda Coutinho, João Durães, Frederico Santos, Ana Alves, Marco Silva, and João Cunha. Challenges and Solutions from an Embedded Programming Bootcamp. In First International Computer Programming Education Conference (ICPEC 2020). Open Access Series in Informatics (OASIcs), Volume 81, pp. 2:1-2:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{amaro_et_al:OASIcs.ICPEC.2020.2,
  author =	{Amaro, J. Pedro and Barreiros, Jorge and Coutinho, Fernanda and Dur\~{a}es, Jo\~{a}o and Santos, Frederico and Alves, Ana and Silva, Marco and Cunha, Jo\~{a}o},
  title =	{{Challenges and Solutions from an Embedded Programming Bootcamp}},
  booktitle =	{First International Computer Programming Education Conference (ICPEC 2020)},
  pages =	{2:1--2:11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-153-5},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{81},
  editor =	{Queir\'{o}s, Ricardo and Portela, Filipe and Pinto, M\'{a}rio and Sim\~{o}es, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ICPEC.2020.2},
  URN =		{urn:nbn:de:0030-drops-122896},
  doi =		{10.4230/OASIcs.ICPEC.2020.2},
  annote =	{Keywords: Coding Bootcamp, Embedded Programming, Career Change}
}
  • Refine by Author
  • 2 Almeida, José João
  • 2 Henriques, Pedro Rangel
  • 2 Silva, João Carlos
  • 2 Silva, Marco
  • 2 Simões, Alberto
  • Show More...

  • Refine by Classification
  • 2 Applied computing → Education
  • 2 Social and professional topics → Computing education
  • 2 Theory of computation → Complexity theory and logic
  • 2 Theory of computation → Integer programming
  • 1 Applied computing → Transportation
  • Show More...

  • Refine by Keyword
  • 1 Affinity
  • 1 Behavior trees (BT)
  • 1 COMUNICA
  • 1 Career Change
  • 1 Code generation
  • Show More...

  • Refine by Type
  • 15 document
  • 1 volume

  • Refine by Publication Year
  • 5 2020
  • 5 2022
  • 3 2021
  • 2 2023
  • 1 2018

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 Imprint Privacy Contact