Generality versus Specificity: An Experience with AI and OR Techniques

Pascal Van Hentenryck, Jean-Philippe CarillonAAAI 1988

Abstract

In the field of combinatorial optimization, researchers have traditionally faced a stark choice between general-purpose tools that are easy to model but computationally inefficient, and specialized algorithms that are highly performant but difficult to develop and maintain. This paper, originally presented at AAAI-88, investigates whether Constraint Logic Programming (CLP) can bridge this gap. By evaluating the "warehouse location problem," the authors compare traditional Operations Research (OR) techniques and hand-coded procedural programs against the CHIP (Constraint Handling in Prolog) language. The findings suggest that CLP provides a robust middle ground, offering near-procedural efficiency with the declarative ease of high-level modeling.

Introduction

The tension between generality and specificity is a fundamental challenge in computer science. General tools, such as Integer Programming (IP) packages, allow for rapid problem formulation but often struggle with the massive search spaces inherent in NP-complete problems because they obscure the underlying problem structure. Conversely, specialized procedural programs—often written in languages like Pascal—can leverage specific heuristics to achieve high performance, but they are "brittle." A minor change in problem constraints can necessitate a complete rewrite of the specialized codebase.

This study explores the potential of Constraint Logic Programming to resolve this dilemma. By integrating "Consistency Techniques" from Artificial Intelligence into a logic programming framework, the authors demonstrate a method that preserves the declarative nature of general tools while approaching the execution speed of specialized software.

The Benchmark: The Warehouse Location Problem

To test these competing methodologies, the authors utilized the warehouse location problem (WLP). The WLP involves a set of potential warehouse locations and a set of customers. Each location has a fixed construction cost, and each customer-warehouse pair has an associated transportation cost. The goal is to determine which warehouses to open and which customers to assign to them to minimize the total cost.

While seemingly straightforward, the WLP is a discrete combinatorial problem that becomes computationally expensive as the number of locations and customers increases. The authors tested their approaches on two specific instances: a "21-20" instance (21 locations, 20 customers) and a "21-80" instance (21 locations, 80 customers), utilizing the hardware of the era (a SUN 3/160 workstation).

Methodological Approaches

The authors implemented the WLP using three distinct paradigms:

  1. Integer Programming (IP): This traditional OR approach models the problem as a system of linear equations and inequalities. While easy to define, the IP model often results in a "recasting" of the problem logic into a purely mathematical form, which can lead to inefficient search patterns.
  2. Specialized Procedural Program: A custom Branch & Bound algorithm was developed in Pascal, totaling approximately 2,000 lines of code. This program used sophisticated "optimistic" evaluation functions to prune the search tree effectively. While fast, it required several months of development.
  3. Constraint Logic Programming (CHIP): CHIP extends Prolog with domain variables and symbolic constraints. It uses consistency techniques to prune the search space dynamically. A key feature is the element constraint, which allows the system to look ahead and eliminate inconsistent values before they are even tested in the search tree.

Key Insights: The Power of Pruning

The core advantage of the CHIP approach lies in its ability to maintain the problem's inherent logic. In the specialized Pascal program, the developer had to manually code the bounding functions and pruning logic. In CHIP, the natural declarative statement of the problem constraints—combined with the language's built-in consistency techniques—automatically "discovered" the same efficient pruning strategies.

Furthermore, CHIP offered a level of flexibility that procedural code could not match. For instance, adding a "disjunctive constraint" (e.g., a rule stating that two specific warehouses cannot both be open) required only a single additional line of code in CHIP. In the Pascal implementation, such a change would have required significant structural modifications to the search algorithm.

Results and Performance

The experimental results highlighted a significant breakthrough for AI techniques in 1988:

  • Development Efficiency: The CHIP program was approximately two pages long and took only a few days to develop, compared to the months required for the 2,000-line Pascal program.
  • Execution Speed: Despite being a high-level declarative language, CHIP was only 5 to 10 times slower than the hand-optimized Pascal code. For the 21-20 instance, CHIP found and proved the optimal solution in just 20 seconds.
  • Search Space Reduction: The consistency techniques in CHIP allowed it to explore a significantly smaller search tree than traditional backtracking or standard IP solvers.

Conclusion

The paper concludes that AI-based Constraint Logic Programming and traditional OR techniques are complementary. While specialized OR "relaxation" methods remain superior for problems with deep mathematical structures (like the Traveling Salesman Problem), CLP is an ideal tool for complex combinatorial problems where constraints are difficult to model mathematically. By providing a bridge between the ease of general modeling and the performance of specific algorithms, CHIP demonstrated that high-level AI languages could be viable for solving real-world industrial problems.

Summary updated

BibTeX
@inproceedings{hentenryck1988generality,
  author = {Pascal Van Hentenryck and Jean-Philippe Carillon},
  title = {{Generality versus Specificity: An Experience with AI and OR Techniques}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure