Artificial intelligence and operations research: challenges and opportunities in planning and scheduling

Carla P. Gomes

TL;DR

This paper explores the intersection of Artificial Intelligence (AI) and Operations Research (OR) for solving complex planning and scheduling problems. It highlights how combining the rich representational power of AI with the efficient solution methods of OR, particularly through techniques like hybrid solvers and portfolio approaches, can lead to significant improvements in tackling computationally hard problems.

What Problem Does This Paper Address?

The paper addresses the long-standing challenge of solving complex combinatorial problems, specifically in planning and scheduling. Both AI and OR communities have developed powerful techniques, but they often have complementary strengths and weaknesses. AI excels at representing complex real-world scenarios with rich formalisms, but these can lead to intractable problems. OR, on the other hand, offers efficient methods for finding optimal solutions but often relies on simplified, rigid models. The core problem is bridging this gap to develop methods that are both expressive enough to model real-world complexity and efficient enough to find good solutions in a reasonable time.

Methods

The paper discusses several key approaches for integrating AI and OR:

  • Hybrid Solvers: Combining constraint satisfaction (CSP) techniques from AI with linear programming (LP) from OR. This leverages AI's constraint reasoning for domain reduction and OR's LP solvers for optimization.
  • Portfolio Approaches: Creating a collection of different algorithms or multiple runs of the same algorithm to exploit variations in performance. This is particularly effective for stochastic algorithms where runtimes can vary significantly.
  • Randomization and Restarts: Introducing randomness into search procedures (e.g., in variable selection) and using restart strategies to manage "heavy-tailed" cost distributions, which are characterized by a high probability of encountering extremely long runs.
  • Exploiting Problem Structure: Identifying and leveraging inherent structures within problems, similar to how OR uses network flow or LP structures, and how AI uses global constraints.

Datasets

The paper does not explicitly list specific datasets used for training. However, it mentions using "hard combinatorial search problems" from various domains for evaluation, including:

  • Scheduling problems: Specifically, round-robin scheduling problems.
  • Planning problems: Formulated as propositional satisfiability (SAT) problems, including logistics planning.
  • Circuit synthesis problems: Formulated as propositional satisfiability problems.
  • Quasigroup Completion Problem (QCP): A benchmark domain introduced by the authors to study search methods and phase transitions.

Key Insights and Ideas

  • Heavy-Tailed Cost Distributions: A significant finding is that the runtime of many combinatorial search algorithms exhibits "heavy-tailed" distributions. This means there's a non-negligible probability of encountering extremely long runs, which explains the erratic behavior of mean and variance in search performance.
  • Restarts as a Solution: Randomized restarts are shown to be a highly effective strategy for mitigating the negative effects of heavy-tailed distributions, dramatically reducing variance and improving overall performance.
  • Portfolio Advantage: Combining algorithms, especially those with different performance profiles (e.g., one good at quick solutions, another better on harder problems), in a portfolio can yield significant computational advantages, particularly on compute clusters.
  • "Risky" Strategies Can Pay Off: In some cases, strategies that are more "audacious" (higher variance, higher chance of short runs) can outperform more conservative strategies when run in parallel as part of a portfolio.
  • AI and OR Complementarity: The paper strongly advocates for the synergistic benefits of integrating AI's representational richness with OR's optimization power.

Key Results

  • Speedups: The paper reports speedups of "several orders of magnitude" for state-of-the-art complete search procedures on hard, real-world problems through randomization and restarts.
  • Solving Previously Unsolved Problems: The proposed techniques enabled solving problem instances that were previously intractable for backtrack-style procedures.
  • Portfolio Performance: For logistics planning problems, portfolios of depth-first search strategies on multiple processors outperformed best-bound strategies, especially when aiming for a good balance of expected runtime and risk.
  • Round-Robin Scheduling: The randomized approach allowed solving round-robin scheduling problems of size up to 18, whereas deterministic methods could only handle up to size 14.
  • Logistics Planning: The problem size for logistics planning instances solvable by complete methods was extended from 1,141 to 2,160 variables.

Limitations and Future Work

  • Heuristic Dependence: The effectiveness of certain strategies, like restarts, is heavily dependent on the presence of heavy-tailed distributions. The paper notes that not all problems exhibit this behavior (e.g., blocks-world planning).
  • Optimal Cutoff Tuning: Determining the optimal cutoff for restarts can be a trial-and-error process, especially for very hard instances.
  • Future Work: The authors suggest further research into:
  • Formalizing the notion of "robustness" in solutions.
  • Investigating the design of global constraints and good relaxation schemes for primal and dual formulations.
  • Exploring new ways for performing sensitivity analysis based on duality.
  • Applying the randomization and portfolio approaches to other backtrack-style algorithms (e.g., dynamic backtracking).
  • Further understanding the characteristics of combinatorial search problems that lead to heavy-tailed behavior.

Summary updated

Abstract

Both the Artificial Intelligence (AI) and the Operations Research (OR) communities are interested in developing techniques for solving hard combinatorial problems, in particular in the domain of planning and scheduling. AI approaches encompass a rich collection of knowledge representation formalisms for dealing with a wide variety of real-world problems. Some examples are constraint programming representations, logical formalisms, declarative and functional programming languages such as Prolog and Lisp, Bayesian models, rule-based formalism, etc. The downside of such rich representations is that in general they lead to intractable problems, and we therefore often cannot use such formalisms for handling realistic size problems. OR, on the other hand, has focused on more tractable representations, such as linear programming formulations. OR-based techniques have demonstrated the ability to identify optimal and locally optimal solutions for well-defined problem spaces. In general, however, OR solutions are restricted to rigid models with limited expressive power. AI techniques, on the other hand, provide richer and more flexible representations of real-world problems, supporting efficient constraint-based reasoning mechanisms as well as mixed initiative frameworks, which allow the human expertise to be in the loop. The challenge lies in providing representations that are expressive enough to describe real-world problems and at the same time guaranteeing good and fast solutions.
BibTeX
@article{gomes2000artificial,
  author = {Carla P. Gomes},
  title = {{Artificial intelligence and operations research: challenges and opportunities in planning and scheduling}},
  journal = {The Knowledge Engineering Review},
  year = {2000},
  doi = {10.1017/s0269888900001090},
}
Figure