IJCAI 2013 Tutorial
|
When creating software, particularly solvers for the computationally challenging problems arising in many areas of AI, developers frequently explore multiple ways of achieving certain tasks. Often, these alternatives are eliminated or abandoned early in the process, based on the belief that the flexibility afforded by them would be dicult or impossible to exploit later. Programming by Optimization (PbO) is a design paradigm that aims to avoid such premature design choices and to actively develop promising alternatives for parts of the design. Rather than build a single program for a given purpose, software developers specify a rich and potentially large design space of programs. From this specification, programs that perform well in a given use context are generated automatically through powerful machine learning and optimisation techniques. PbO allows human experts to focus on the creative task of imagining possible mechanisms for solving given problems or subproblems, while the tedious job of determining what works best in a given use context is performed automatically, substituting human labor with computation. Furthermore, using PbO, per-instance algorithm selectors and parallel algorithm portfolios can be obtained from the same sequential source.
In this tutorial, we will share the vision of PbO, describe key algorithmic techniques that, fuelled by recent advances in optimization and machine learning, make PbO practical, and illustrate the power of the approach based on several case studies. Specifically, we will survey and explain state-of-the-art methods for automated algorithm con guration (which optimize algorithm parameters for a particular distribution of problem instances), portfolio-based algorithm selection (which select between different algorithms in an instance-specific way) and automated portfolio construction (which identify sets of complementary algorithms or parameter configurations). We will also discuss practical tools that facilitate PbO-based software development. Our application examples and case studies, taken from the recent literature, illustrate how the use of PbO and the computer-aided algorithm design techniques it is based on resulted in substantial improvements of the state of the art (often by orders of magnitude) for various challenging computational problems, including SAT-based software verification, planning and timetabling, supervised machine learning, as well as mixed integer programming -- perhaps the most widely used approach for solving optimization problems in industry. Our tutorial is aimed at AI researchers interested in using the PbO approach and the practical tools that support to better realize the performance potential inherent in their algorithmic ideas.
The slides shown at the tutorial in Beijing can be found here and can be used freely for non-commercial purposes; of course, we'd love to hear from you if you find them useful.
Holger Hoos is a Professor for Computer Science at the University of British Columbia in Vancouver (Canada), where he also holds an appointment as an Associate of the Peter Wall Institute for Advanced Studies. His main research interests span empirical algorithmics, artificial intelligence, bioinformatics and computer music. He is known for his work on the automated design of high-performance algorithms and on stochastic local search methods. Holger is a co-author of the book Stochastic Local Search: Foundations and Applications, and his research has been published in numerous book chapters, journals, and at major conferences in artificial intelligence, operations research, molecular biology and computer music. With his co-authors, he has received numerous best paper awards, including two IJCAI-JAIR Best Paper Prizes and a Distinguished Scholar in Residence position at UBC's Peter Wall Institute for Advanced Studies in 2010. He currently serves as President of the Canadian AI Association (CAIAC), as Associate Editor of the Journal of AI Research, as Area Editor for the Journal of Heuristics and as Editorial Board Member for the Journal on Satisfiability, Boolean Modeling and Computation. Holger regularly teaches courses at all levels at UBC; he has also given tutorials at various conferences (including IJCAI-03, AAAI-04, SLS-09, LION-10 and PPSN-12) and is regularly invited to speak at conferences (e.g., ICAPS 2010, MIC 2011), academic institutions (e.g., Harvard, MIT, University of Toronto) and industrial research laboratories (e.g.,AT&T Research, Google Research, Microsoft Research). Currently, his group is helping UBC to produce better exam timetables, Actenum Inc. to increase production efficiency in the oil and gas industry, and IBM to improve their CPLEX optimisation software.
Frank Hutter is an Assistant Professor at the Computer Science Department of Freiburg University (Germany). Frank's research focuses on the use of machine learning and optimization for improving algorithms for solving NP-hard problems. His 2009 PhD thesis at the University of British Columbia (UBC, in Vancouver, Canada) focused on algorithm configuration and received the CAIAC doctoral dissertation award for the best PhD thesis in Artificial Intelligence completed at a Canadian University that year. With his coauthors, he has received best paper awards from JAIR, SLS and LION, and numerous medals for the portfolio-based SAT solver SATzilla at the International SAT Competition (2007-12). Frank worked as part of the science education initiative of Nobel laureate Carl Wieman for one year to improve UBC's undergraduate AI curriculum, taught the introductory AI course at UBC, and is currently teaching a seminar on algorithm configuration at Freiburg University. He has recently given invited presentations at several institutions, including MIT, Google, Microsoft Research, and IBM Research.
Kevin Leyon-Brown is an Associate Professor in Computer Science at the University of British Columbia in Vancouver (Canada). He holds a PhD and M.Sc. from Stanford University (2003; 2001) and a B.Sc. from McMaster University (1998). Much of his work is at the intersection of computer science and microeconomics, addressing computational problems in economic contexts and incentive issues in multiagent systems. He also studies the application of machine learning to the automated design and analysis of algorithms for solving hard computational problems. He has co-written two books, Multiagent Systems" and "Essentials of Game Theory", and over eighty peer-refereed technical articles. With his coauthors, he has received paper awards from JAIR, ACM-EC, AAMAS and LION, and numerous medals for the portfolio-based SAT solver SATzilla at the International SAT Competition (2003-12). He was program chair for the ACM Conference on Electronic Commerce (ACM-EC) in 2012, and serves as an associate editor for the Journal of Artificial Intelligence Research (JAIR), the Arti cial Intelligence Journal (AIJ), and ACM Transactions on Economics and Computation. He split his 2010-11 sabbatical between Makerere University in Kampala, Uganda, and the Institute for Advanced Studies at Hebrew University in Jerusalem, Israel. He has served as a consultant for Trading Dynamics Inc., Ariba Inc., Cariocas Inc., and Auctionomics, Inc., and was scientific advisor to Zite Inc until it was acquired by CNN in 2011. He teaches courses on Artificial Intelligence, Multiagent Systems, and Computers & Society at UBC, and in January will co-teach a Coursera course on Game Theory with two Stanford professors; over 100,000 students are registered so far.
Links (further information, software)
Further material on the tutorial topic by the
presenters include a CACM
article on programming by optimization,
a JAIR
article on algorithm configuration
and a JAIR
article on the portfolio-based algorithm selection approach SATzilla (which
received the 2010 IJCAI/JAIR Best Paper Prize).
Further PbO-related information and resources (including software):
Please send any questions, concerns or comments to Holger Hoos, Frank Hutter or Kevin Leyton-Brown