Invited Speakers

CPAIOR 2011 features invited talks by:

Prof. Craig Boutilier

Lecture: Preference Elicitation and Preference Learning in Social Choice

Social choice has been the subject of intense investigation within computer science, AI, and operations research, in part because of the ease with which preference data from user populations can now be elicited, assessed, or estimated in online settings. In many domains, the preferences of a group of individuals must be aggregated to form a single consensus recommendation, placing us squarely in the realm of social choice.

I argue that the application of social choice models and voting schemes to domains like web search, product recommendation and social networks places new emphasis, in the design of preference aggregation schemes, on issues such as: articulating decision criteria suitable to the application at hand; approximate winner determination; incremental preference elicitation; learning methods for models of population preferences; and more nuanced analysis of the potential for manipulation.

In this talk, I'll provide an overview of some of these challenges and outline some of our recent work tackling of them, including methods for: learning probabilistic models of population preferences from choice data; robust optimization (winner determination) in the presense of incomplete user preferences; and incremental vote/preference elicitation for group decision making. Each of these poses interesting modeling and optimization challenges that are best tackled using a combination of techniques from AI, operations research, and statistics.

Craig Boutilier is a Professor of Computer Science at the University of Toronto. He received his Ph.D from Toronto in 1992, and joined the faculty of University of British Columbia in 1991 (where he remains an Adjunct Professor). He returned to Toronto in 1999, and served as Chair of the Department of Computer Science from 2004-2010. Boutilier was a consulting professor at Stanford University from 1998-2000, a visiting professor at Brown University in 1998, and a visiting professor at Carnegie Mellon University in 2008-09. He served on the Technical Advisory Board of CombineNet, Inc. from 2001 to 2010.

Boutilier's has published over 170 refereed articles covering topics ranging from knowledge representation, belief revision, default reasoning, and philosophical logic, to probabilistic reasoning, decision making under uncertainty, multiagent systems, and machine learning. His current research efforts focus on various aspects of decision making under uncertainty: preference elicitation, mechanism design, game theory and multiagent decision processes, economic models, social choice, computational advertising, Markov decision processes and reinforcement learning.

Boutilier served as Program Chair for both the 16th Conference on Uncertainty in Artificial Intelligence (UAI-2000) and the 21st International Joint Conference on Artificial Intelligence (IJCAI-09). He is Associate Editor-in-Chief of the Journal of Artificial Intelligence Research (JAIR). Boutilier is a Fellow of the Association for the Advancement of Artificial Intelligence (AAAI). He has been awarded the Isaac Walton Killam Research Fellowship and an IBM Faculty Award. He also received the Killam Teaching Award from the University of British Columbia in 1997.

Prof. Ian Gent

Lecture: Propagation in Constraints: How One Thing Leads To Another

At a conference such as CPAIOR, we have experts from many different approaches to searching huge combinatorial spaces. Much of what we all do is common, for example similar search methods, heuristics, and learning techniques. So what is it that is essentially different about Constraint Programming in particular? One answer is the power and diversity of constraint propagation algorithms. By contrast, other search disciplines often rely on just one propagation technique, such as unit propagation in SAT.

So to paraphrase the property expert, for the duration of this talk I'll say that the three most important aspects of Constraint Programming are "Propagation, Propagation, Propagation." I'll talk about all three. First, what Propagation is and the theory of how propagation algorithms work. Second, how Propagation forms the beating heart of a modern constraint solver, typically throwing away a lot of the theory in the process. And third, some aspects of Propagation in constraints being researched right now.

I hope to bring out some of the beauty and surprises in propagation. I also hope to show how ideas from one discipline have propagated to another, for example the introduction of watched literals from SAT into Constraint Programming. I also hope one propagation will lead to another as some of these lovely ideas propagate again.

Ian Gent is Professor of Computer Science at St Andrews University, Scotland, where he has been since 1999. He earned his PhD with Tony Cohn at Warwick University in 1993. Most of his research has been on combinatorial search in constraint systems. Within this he has focussed on some specific topics, such as symmetry in search, the design of constraint solvers, and on constraint propagation techniques. He has served on numerous committees, for example as Programme Chair of the Constraint Programming conference CP 2009. On a good day he can juggle five balls, and on a very good day figure out some way to get juggling into a technical talk.

Prof. Andrea Lodi

Lecture: On Bilevel Programming and its Impact in Branching, Cutting and Complexity

Bilevel programming is a rich paradigm to express a variety of real-world applications including game theoretic and pricing ones. However, what we are interested in this talk is to discuss the bilevel nature of two of the most crucial ingredients of enumerative methods for solving combinatorial optimization problems, namely branching and cutting.

Specifically, we discuss a new branching method for 0-1 programs called interdiction branching [Lodi, Ralphs, Rossi, Smriglio 2011] that exploits the intrinsic bilevel nature of the problem of selecting a branching disjunction. The method is designed to overcome the difficulties encountered in solving problems for which branching on variables is inherently weak. Unlike traditional methods, selection of the disjunction in interdiction branching takes into account the best feasible solution found so far.

On the cutting plane side, we examine the nature of the so-called separation problem, which is that of generating a valid inequality violated by a given real vector, usually arising as the solution to a relaxation of the original problem. We show that the problem of generating a maximally violated valid inequality often has a natural interpretation as a bilevel program [Lodi, Ralphs, Woeginger 2011]. In some cases, this bilevel program can be easily reformulated as a single-level mathematical program, yielding a standard mathematical programming formulation for the separation problem. In other cases, no reformulation exists yielding surprisingly interesting examples of problems arising in the complexity hierarchies introduced by [Jeroslow 1985].

Andrea Lodi got the PhD in System Engineering from the University of Bologna in 2000 and he has been Herman Goldstine Fellow at the IBM Mathematical Sciences Department, NY in the period 2005-2006. He is currently full professor of Operations Research at DEIS, University of Bologna since 2007. Andrea Lodi main research interests are in the closely related areas of Integer Programming and Combinatorial Optimization where he gave contributions on the design and analysis both theoretical and empirical of algorithms for NP-hard problems. He is also interested in hybrid methods integrating Constraint and Integer Programming. He is author of more than 50 publications in the top journals of the field of Mathematical Programming and he serves as Associated Editor for several prestigious journals in the area as Mathematical Programming Series A, INFORMS Journal of Computing, Management Science and Mathematical Programming Computation. He was also Editor-in-Chief of Optima, the Newsletter of the Mathematical Programming Society in the period 2007-2010. Finally, Andrea Lodi is, since 2006, consultant and part-time member of the IBM CPLEX (former ILOG CPLEX) R&D team which develops the world-leading general-purpose software for Integer Programming CPLEX.