3.  Abstracts and Statements

• Baptista, Luis and Marques-Silva Joćo; The Interplay of Randomization and Learning on Real-World Instances of Satisfiability

• Davenport, Andrew; Cooperative Strategies for Solving Bicriteria sparse Multiple Knapsack Problem

• Grosskreutz, Henrik; Logic-based High-level Robot Control

• Hogg, Tad; Parallel Search Using Portfolios

• Hoos, Holger and O'Neil, Kevin; Stochastic Local Search Methods for Dynamic SAT: An Initial Investigation

• Horsch, Michael and Havens, William S.; Techniques for approximating solution probabilities for constraint satisfaction problems

• Irgens, Morten and Jackson, Ken W.; Randomization in local search for k-sat: The Simulated Annealing case

• Matsuo, Yutaka; Fast Hypothetical Reasoning by Parallel Processing

• Rish, Irina; Probabilistic Models of Computing

• Ruml, Wheeler; On-line Learning of Statistical Models of a Search Space to Adaptively Guide Optimization Algorithms

• Russell, Stuart; AI and Monte Carlo Methods

• Santos, Eugene Jr.; Portfolios of Algorithms to Exploit Structure and Randomization in Hard Computational Problems

• Shimony, Solomon; Estimating Constraint Network Solution Count: Probabilistic and Deterministic Schemes

• Steinberg, Lou; Utility-Guided Search of  Stochastically Generated Trees

• Walsh, Toby; Portfolios, Randomization, Discrepancy Strategies, and Problem Structure

• Zilberstein, Sholomo; Dynamic Scheduling of Progressive Processing Plans

  The Interplay of Randomization and Learning on Real-World Instances of Satisfiability

Luis Baptista and Joćo Marques-Silva  
Technical University of Lisbon

Recent work on the Satisfiability Problem (SAT) has provided strong empirical and theoretical evidence of the advantages of applying randomization and restarts in solving satisfiable problem instances. This paper addresses the interaction between randomization, with restart strategies, and learning, an often crucial technique for proving unsatisfiability. We use instances of SAT from the hardware verification domain to provide evidence that randomization can indeed be essential in solving real-world satisfiable instances of SAT. More interestingly, our results indicate that randomized restarts and learning may cooperate in proving both satisfiability and unsatisfiability. Finally, we utilize and expand the idea of algorithm portfolio design to propose an alternative approach for solving hard unsatisfiable instances of SAT.
(Extended abstract)

  Cooperative Strategies for Solving Bicriteria sparse Multiple Knapsack Problem

  Andrew Davenport  
IBM T. J. Watson Research Center

One of the major goals of a production facility is to utilize its inventory in the best possible way to satisfy demand. In make-to-order production systems, such as the process industry, a surplus inventory accumulates due to cancellations of orders and rejection of production units for failing to satisfy quality requirements. Clearly, it is to the advantage of the production facility to utilize this surplus inventory before planning its production activates. This raises the problem of assigning a list of orders to the production units in the inventory.  The objectives are both maximizing the total amount of orders that are assigned, and minimizing total waste of production units. Manufacturability considerations such as the compatibility of orders and production units in terms of quality, size, etc. impose additional assignment constraints.  As production operations involve more complex processes and a larger product variety, the problem becomes more constrained.  The bicriteria sparse multiple knapsack problem that we consider in this study is motivated by this application.

For complex, real world optimization problems such as the one outlined above,  it is often difficult to design heuristic algorithms which exhibit uniformly superior performance for all problem instances.  As a result it becomes necessary to tailor the algorithms based on the problem instance.  We introduce the use of a cooperative problem solving team of heuristics that evolves algorithms for a given problem instance. The efficacy of this method is examined by solving six difficult instances of a bicriteria sparse multiple knapsack problem based on real world instances.

We focus on the use of a team of heuristic algorithms, which cooperate to generate non-dominated solutions for this problem in a short computation time.  Although there exist several heuristic approaches for solving multiple knapsack problems there does not exist a single dominant algorithm. Moreover, the performances of the heuristics vary by problem instance and as a result a specific heuristic will often demonstrate poor aggregate performance over a set of problem instances.  However, if the heuristics were allowed to cooperate with each other so that:

• the solution generated by one heuristic can be subsequently improved by another or
• the most appropriate subset of heuristics can be used to construct solutions for a given problem instance

then the aggregate performance of a collection of cooperating heuristics over a set of problem instances may be greatly improved. For this purpose we have developed a collection of fast heuristics and incorporated them in an A-team architecture, which provides a computational framework for implementing cooperation strategies among heuristics.  The A-team architecture has been used to obtain good feasible solutions to various combinatorial optimization problems such as the TSP, and scheduling problems arising in steel and paper manufacturing industry.

The solutions generated using this approach on our problem instances were shown to be superior to those derived from using these heuristics individually, and to feasible solutions derived from integer programming techniques and a tabu search implementation.

We have found the bicriteria sparse multiple knapsack problem to be a challenging problem to solve for the following reasons:

• the problem is hard to solve for each of its optimization criterion taken alone;
• a large number of heuristics exist in the literature for solving the problem for each individual criterion; however no one heuristic technique is dominant across all problem instances.

We believe that the A-team is a suitable approach for this type of problem because:

• the architecture allows us to run a portfolio of heuristics on a single problem instance to generate the best individual heuristic solution;
• the heuristics for different optimization criteria cooperate towards generating Pareto optimal solutions for each instance, by performing a search in the sequence of heuristic applications.

The experimental evaluation supported these conclusions: the solutions generated by the cooperative strategy were always better than the best solution generated by the individual heuristics, and no single sequence of heuristic applications performed by the A-team was dominant across all problem instances. Thus we believe that the cooperative problem solving strategy embodied by the A-team architecture is a promising approach for tackling hard, multi-criteria combinatorial optimization problems.

Logic-based High-level Robot Control

Henrik  Grosskreutz
Aachen University of Technology, Germany

I am a PhD. student in Aachen, Germany. My research is concerned with logic-based high-level robot control. More specifically, I am working on extensions of the high-level plan language GOLOG, whose semantics relies on the situation calculus. In order to allow for uncertainty, which is ubiquitous in real robotics application, I am working on probabilistic extensions of the situation calculus and the language Golog, and have so me encouraging preliminary result. The work is related to the work of Bacchus, Halpern and Levesque titled "Reasoning about Noisy Sensors and Effectors in the Situation Calculus" which appeared in Artificial Intelligence 111. I am also looking for ways to make use of Monte-Carlo methods to speed up prediction results through approximation.

  Parallel Search Using Portfolios

Tad Hogg  
Xerox  Palo Alto Research Center

  Combinatorial search problems can require exponentially growing search cost as the size of the problems increase. Fortunately, a variety of heuristic methods solve many such problems much more rapidly than would be expected from the increasing size of the search space. Such heuristics often have different strengths; so running them in parallel can give good performance across a wider range of problems than any individual heuristic. Such approaches, analogous to portfolios in financial markets, can simultaneously improve expected performance and reduce the performance variation. This paper describes this approach and directions for future work involving cooperative methods and alternate computational devices.
(Extended abstract)

Stochastic Local Search Methods for Dynamic SAT: An Initial Investigation

Holger Hoos and Kevin O'Neill  
University of British Columbia

  We introduce the dynamic SAT problem, a generalisation of the satisfiability problem in propositional logic, which allows changes of a problem over time. DynSAT can be seen as a particular form of a dynamic CSP, but considering results and recent success in solving conventional SAT problems, we believe that the conceptual simplicity of SAT will allow us to more easily devise and investigate high-performing algorithms for DynSAT than for dynamic CSPs. In this article, we motivate the DynSAT problem, discuss various formalizations of it, and investigate stochastic local search (SLS) algorithms for solving it. In particular, we apply SLS algorithms which perform well on conventional SAT problems to dynamic problems and we analyze and characterize their performance empirically; this initial investigation indicates that the performance differences between various algorithms of the well-known WalkSAT family of SAT algorithms generally carry over when applied to DynSAT. We also study different generic approaches of solving DynSAT problems using SLS algorithms and investigate their performance differences when applied to different types of DynSAT problems.
(Paper)

  Techniques for approximating solution probabilities for constraint satisfaction problems

Michael C. Horsch and William S. Havens
Simon Fraser University

We have been developing this technique, which provides a direct relationship between techniques in constraint reasoning and probabilistic reasoning.  We have very good results with respect to reducing search costs such as consistency checks, and the number of backtracks, having demonstrated an improvement over some existing heuristics by up to several orders of magnitude. Our success does not come without a price: computing solution probabilities can be quite a bit more expensive than the actual search costs.  We are currently investigating techniques by which the accuracy of our approximations can be traded off against computational costs, preferably in a utility based, flexible manner.  We are currently investigating a strongly related technique based on probabilistic relaxation, due to Peleg.  Theoretical and empirical studies are on going, but our belief is that this technique can be employed in stochastic local search. We would be interested to share our results with others at the workshop, as well as to gain a deeper understanding of the issues of the workshop as they relate to our work.

  Randomization in local search for k-sat: The Simulated Annealing case

Morten Irgens and Ken W. Jackson
Simon Fraser University

The Metropolis and Simulated came out of the idea of optimization by probabilistic sampling using Markov chains. These algorithms converge in the limit to the optimal solution of the corresponding optimization problem given they respect certain conditions. Both the guarantees and the conditions are of limited value for real-world versions of the algorithms.

While considerable energy has been spent on designing good temperature schedules for the Simulated Annealing algorithm, we show evidence that for randomly generated k-sat problems the shape of monotonic schedules are of little importance.  The almost only interesting of a schedule is its temperature level.   As a consequence, we show that cooling and heating perform almost equally well for this class of problems.  Next, we show evidence for an optimal temperature level for the Metropolis algorithm (or alternatively, that there is an optimal constant temperature for simulated annealing), and that cooling schedules don't beat this.  We show that for randomly generated k-sat problems, this is independent of problem size and hardness.  Finally, we show that the shapes of non-monotonic schedules are important.   We show that there is an optimal period for oscillating temperatures, and that for k-sat problems, this is independent of problem size and hardness.  We show that this period is very low, and argue that this gives us insight into the nature of randomly generated k-sat problems.

  Fast Hypothetical Reasoning by Parallel Processing

Yutaka Matsuo
University of Tokyo

 In this paper, we develop a new framework for hypothetical reasoning that uses parallel software processors. Our earlier SL method, which can find a near-optimal solution for cost-based hypothetical reasoning in polynomial time (with respect to problem size), uses both linear programming and nonlinear programming techniques. In the new method, these techniques are realized as the interaction of parallel processors. Taking this approach, we may generalize related methods such as the breakout method or Gu's nonlinear optimization method for SAT problems, and introduce two superior algorithms. One algorithm is similar to the breakout method, and the other achieves good-quality solutions by adding new processors during search iterations. (Paper)

Probabilistic Models of Computing

  Irina Rish  
IBM T. J. Watson Research Center

 (Extended statement)  

  On-line Learning of Statistical Models of a Search Space to Adaptively Guide Optimization Algorithms

  Wheeler Ruml  
Harvard University

I am a graduate student in Computer Science at Harvard University, with research interests in heuristic search and combinatorial optimization. My current work (joint with Avi Pfeffer) focuses on on-line learning of statistical models of a search space to adaptively guide optimization algorithms. This draws on work from reinforcement learning and utility-based decision-making, attempting to apply those ideas to stochastic search. These techniques provide a rational way to represent, integrate, and exploit information gained during the course of a search, and trade that exploitation against exploring new parts of the solution space. Unfortunately, the empirical testing is only just getting underway, so I am unable to submit a paper to the workshop, but I am still strongly interested in attending.

I have done previous work on stochastic search methods for graph bisection, boolean satisfiability, and number partitioning, focusing on exploitation of variance to achieve high performance in a limited-time context, at the expense of incompleteness (joint work with Stuart Shieber and with Joe Marks of Mitsubishi Electric Research Labs). I also have related interests in the characterization of search spaces, and the use of visualization to help understand them.

  AI and Monte Carlo Methods

Stuart Russell  
University of California Berkeley

   
Markov chain Monte Carlo methods have developed over the last few years into a powerful tool for Bayesian statistics. In this talk I will consider their possible roles in AI.

Portfolios of Algorithms to Exploit Structure and Randomization in Hard Computational Problems