Université de Montréal
Margarida Carvalho has a B.Sc. and a M.Sc. in mathematics. In 2016, she obtained her Ph.D. in Computer Science by the University of Porto which was later awarded the EURO Doctoral Dissertation Award 2018 by The Association of European Operational Research Societies. During her Ph.D. she was a Research Visitor at DEI (Università di Bologna) and at CORE (Université catholique de Louvain). In 2017, she became an IVADO fellow at Polytechnique Montréal. Currently, Margarida Carvalho is an Assistant Professor at Université de Montréal and she holds a FRQ–IVADO Research Chair in Data Science for Combinatorial Game Theory. Her fields of expertise are game theory and mixed integer programming, focusing mainly in algorithmic design, computational complexity, and applications in health-care.
Integer programming games (IPGs) are a class of problems that can suitably model non-cooperative interactions between decision makers (players). Under such formulations, each player goal in the game is described by a parametric integer program where interactions between players are reflected in their objective functions. This talk will begin with the description of IPGs, the challenge they represent and an algorithmic framework to solve them that integrates ideas of normal-form games. The notion of solution to IPGs will motivate the second part of this talk, where refinements will be discussed, in particular, in the context of policy making for the kidney exchange game. In this context, the problem of integrating (patients) fairness will be addressed as a constraint satisfaction problem.
University of Oxford & TU Wien
Georg Gottlob is a Royal Society Research Professor at the Computer Science Department of the University of Oxford, a Fellow of St John's College, Oxford, and an Adjunct Professor at TU Wien. His interests include knowledge representation, database theory, query processing, web data extraction, and (hyper)graph decomposition techniques. Gottlob has received the Wittgenstein Award from the Austrian National Science Fund and the Ada Lovelace Medal (UK). He is an ACM Fellow, an ECCAI Fellow, a Fellow of the Royal Society, and a member of the Austrian Academy of Sciences, the German National Academy of Sciences, and the Academia Europaea. He chaired the Program Committees of IJCAI 2003 and ACM PODS 2000 and is on the Editorial Boards of JACM and JCSS. He was a founder of Lixto, a web data extraction firm acquired in 2013 by McKinsey & Company. In 2015 he co-founded Wrapidity, a spin out of Oxford University based on fully automated web data extraction technology developed in the context of an ERC Advanced Grant. Wrapidity was acquired by Meltwater, an internationally operating media intelligence company. More recently, Gottlob co-founded the Oxford spin-out DeepReason.ai, which provides knowledge graph and rule-based reasoning software to customers in various industries.
In the context of constraint satisfaction problems (CSPs) and database queries, the hypertree decomposition method is used for faster CSP solving and for query optimization, whereby problem instances having a low hypertree width (i.e., a low degree of cyclicity) can be recognized and decomposed automatically, and efficiently evaluated. CSPs and queries having bounded hypertree width are also highly parallelizable. The notion of Hypertree decomposition was introduced in 1999. This talk reviews - in form of questions and answers - the main relevant concepts and algorithms and surveys selected related work including applications and test results.
Technische Universität Berlin, Zuse Institute Berlin
In this talk we will consider the deliberate restarting of algorithms, a meta technique, in order to improve the algorithm’s performance, e.g., convergence rates or approximation guarantees. One of the major advantages is that restarts are relatively black box, not requiring any (significant) changes to the base algorithm that is restarted or the underlying argument, while leading to potentially significant improvements, e.g., from sublinear to linear rates of convergence. Restarts are widely used in different fields and have become a powerful tool to leverage additional information that has not been directly incorporated in the base algorithm or argument. We will review restarts in various settings from continuous optimization, discrete optimization, and submodular function maximization where they have delivered impressive results.
Joint CPAIOR/SoCS talk
Professor Peter J. Stuckey is a Professor in Faculty of Information Technology at Monash University and Fellow of the Association for the Advancement of Artificial Intelligence. He is a pioneer in the field of constraint programming: He is an author of CLP(R), one of the first three constraint programming systems ever devised; he helped define the theoretical underpinnings of the field with a paper describing the formal semantics, and co-wrote the first textbook in the field. He has driven the development of MiniZinc the most widely used constraint programming modelling language. And devised the "lazy clause generation" (LCG) approach to discrete optimization which defines the state-of-the-art for very many discrete optimization problems. This work was awarded the Google Australia Eureka Prize for Innovation in Computer Science and the Woodward Medal.
Multi-Agent Path Finding (MAPF) is a problem that requires one to compute a set of collision-free paths for a team of moving agents. The problem appears in variety of practical applications including warehouse logistics, traffic management, aircraft towing and computer games. The general version of the problem (minimizing makespan or sum of path costs, on graphs with parallel actions and rotations) is known to be NP-hard. One of the leading methods for solving MAPF optimally, employs a strategy known as Conflict-based Search (CBS). The central idea is to plan paths for each agent independently and resolve collisions by branching the current plan. Each branch is a new candidate plan wherein one agent or the other is forced to find a new path that avoids the selected collision. When we examine CBS from an optimisation perspective, it is clearly a form of (Logic-based) Benders Decomposition. This begs the question: can we use combinatorial optimisation techniques to tackle the MAPF problem efficiently? In this talk I will show two approaches: the first uses core-guided search together with a nogood learning Constraint Programming solver; the second uses Branch-and-Cut-and-Price together with a MIP solver. Both methods prove to be highly competitive to previous CBS approaches.