Margarida Carvalho
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.
Algorithmic approaches for integer programming games and a story on policy making
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.
Georg Gottlob
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.
Hypertree Decompositions: Questions and Answers
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.
Sebastian Pokutta
Technische Universität Berlin, Zuse Institute Berlin
Sebastian Pokutta is the Vice President of the Zuse Institute Berlin (ZIB) and a Professor of Mathematics at TU Berlin with a research focus on Artificial Intelligence and Optimization. Having received both his diploma and Ph.D. in mathematics from the University of Duisburg-Essen in Germany, Pokutta was a postdoctoral researcher and visiting lecturer at MIT, worked for IBM ILOG, and Krall Demmel Baumgarten. Prior to joining ZIB and TU Berlin, he was the David M. McKenney Family Associate Professor in the School of Industrial and Systems Engineering and an Associate Director of the Machine Learning @ GT Center at the Georgia Institute of Technology as well as a Professor at the University of Erlangen-Nürnberg. Sebastian received the David M. McKenney Family Early Career Professorship in 2016, an NSF CAREER Award in 2015, the Coca-Cola Early Career Professorship in 2014, the outstanding thesis award of the University of Duisburg-Essen in 2006, as well as various Best Paper awards. Pokutta's research is situated at the intersection of Artificial Intelligence and Optimization, currently with a particular focus on Conditional Gradient approaches, combining Machine Learning and Discrete Optimization, as well as exploring the limits of computation in alternative models of complexity. Pokutta's applied work includes stowage optimization problems for inland vessels, oil production problems, clearing of electricity markets, order fulfillment problems, warehouse location problems, simulation of autonomous vehicle fleets, portfolio optimization problems, optimal liquidity management strategies, and predictive pregnancy diagnostics.
Restarting Algorithms: Sometimes there is Free Lunch
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.
Peter Stuckey
Monash University
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.
Combinatorial Optimisation for Multi-Agent Path Finding
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.