Invited Speakers

• Robert Bixby, ILOG Inc.
  The New Generation of Mixed-Integer Programming Codes
  Dantzig, Fulkerson, and Selmer Johnson laid the foundation for modern-day integer programming computation in their 1954 paper using linear programming methods to solve a certain 49-city traveling salesman problem. In the 1960s, Gomory made important theortical contributions to the subject, and in the 1970s the practical use of integer programming took a significant step forward with the introducion of two powerful, commercial integer programming codes: MPSX/370 (IBM) and UMPIRE (SCICONIC). In the years that followed, integer programming computational research flourished, with important work by Groetschel, Ellis Johnson, Padberg, Wolsey and others. However, virtually all of that work remained isolated in largely academic codes. From the mid 1970s through the late 1990s, commercial integer programming codes got faster, but only because linear programming and computing machines got faster; the underlying integer-programming methodolgies remained essentially unchanged. In the last several years, that situation has changed dramatically, with the development of a newer generation of commerical codes incorporating most of the important computational advances from the previous two decades. The real achievement of these codes, and a central theme of this talk, is the integration of a wide collection of methods and ideas in one algorithmic framework with robust default behavior, capable of solving a significant fraction of integer-programming instances encountered in practice.
  
• Ronen Brafman, Ben-Gurion University, Israel
  Preference-Based Constrained Optimization with CP-Nets
  Consider the problem of providing users with tools that enable optimal selection of configurable products, such as, vacation packages, personal computers, or even a personalized newspaper. These configuration problems can be formulated abstractly as constrained-optimization problems: Find the best (given the user’s preferences) vacation satisfying various constraints (duration, price, etc.). This class of constrained optimization problem, which we refer to as "preference-based constrained optimization" differs from the classical constrained optimization problems studied in applied mathematics and OR. Rather than real-valued variables we are mostly dealing with discrete variables with finite domains, and instead of real-value objective functions, we have the amorphous notion of "user preferences". To formulate this class of problems properly, we need to more carefully specify their input, bearing in mind that this information must be realistically obtainable from the type of users we have in mind. We must also provide efficient solution algorithms, so that this approach is usable in on-line applications. In this talk I will describe CP-networks, a knowledge-representation structure that exploits the notion of conditional preferential independence to enable convenient preference elicitation and representation. I will explain their basic properties and I will show how we can do preference-based constrained optimization given a CP-net efficiently. To illustrate these ideas, I will describe and demonstrate a tool we recently built for personalization of synchronized rich-media presentations.
  
• Henry Kautz, University of Washington, USA
  Toward a Universal Inference Engine
  In the early days of AI some researchers proposed that intelligent problem solving could be reduced to the application of general purpose theorem provers to an axiomatization of commonsense knowledge. Although automated first-order theorem proving was unwieldy, general reasoning engines for propositional logic turned out to be surprisingly efficient for a wide variety of applications. Still many problems of interest to AI involve probabilities or quantification, and would seem to be beyond propositional methods. However, recent research has shown that the basic backtrack search algorithm for satisfiability generalizes to a strikingly efficient approach for broader classes of inference. We may be on the threshold of achieving the old dream of a universal inference engine.