A constraint-based architecture for local search

ABSTRACT

Combinatorial optimization problems are ubiquitous in numerous practical applications. Yet most of them are challenging, both from computational complexity and programming standpoints. Local search is one of the main approaches to address these problems. However, it often requires sophisticated incremental algorithms and data structures, and considerable experimentation. This paper proposes a constraint-based, object-oriented, architecture to reduce the development time of local search algorithms significantly. The architecture consists of declarative and search components. The declarative component includes invariants, which maintain complex expressions incrementally, and differentiable objects, which maintain properties that can be queried to evaluate the effect of local moves. Differentiable objects are high-level modeling concepts, such as constraints and functions, that capture combinatorial substructures arising in many applications. The search component supports various abstractions to specify heuristics and meta-heuristics. We illustrate the architecture with the language Comet and several applications, such as car sequencing and the progressive party problem. The applications indicate that the architecture allows for very high-level modeling of local search algorithms, while preserving excellent performance.

REFERENCES

• 1: Bowen Alpern , Roger Hoover , Barry K. Rosen , Peter F. Sweeney , F. Kenneth Zadeck, Incremental evaluation of computational circuits, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.32-42, January 22-24, 1990, San Francisco, California, United States
• 2: A. Andreatta. A framework for the development of local search heuristics with an application to the phylogeny problem, 1997.
• 3: Nicolas Beldiceanu , Mats Carlsson, Revisiting the Cardinality Operator and Introducing the Cardinality-Path Constraint Family, Proceedings of the 17th International Conference on Logic Programming, p.59-73, November 26-December 01, 2001
• 4: Alan Borning, The Programming Language Aspects of ThingLab, a Constraint-Oriented Simulation Laboratory, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.4, p.353-387, Oct. 1981 [doi>10.1145/357146.357147]
• 5: Philippe Codognet , Daniel Diaz, Yet Another Local Search Method for Constraint Solving, Proceedings of the International Symposium on Stochastic Algorithms: Foundations and Applications, p.73-90, December 13-14, 2001
• 6: Alain Colmerauer, An introduction to Prolog III, Communications of the ACM, v.33 n.7, p.69-90, July 1990 [doi>10.1145/79204.79210]
• 7: M. Dincbas, H. Simonis, and P. Van Hentenryck. Solving the Car Sequencing Problem in Constraint Logic Programming. In ECAI-88, August 1988.
• 8: A. Fink, S. Voss, and D. Woodruff. Building reusable software components for heuristc search, 1998.
• 9: R. Fourer, D. Gay, and B. Kernighan. AMPL: A Modeling Language for Mathematical Programming. The Scientific Press, San Francisco, CA, 1993.
• 10: P. Galinier and J.-K. Hao. A General Approach for Constraint Solving by Local Search. In CP-AI-OR'00, Paderborn, Germany, March 2000.
• 11: Ian P. Gent , Toby Walsh, CSPLIB: A Benchmark Library for Constraints, Proceedings of the 5th International Conference on Principles and Practice of Constraint Programming, p.480-481, October 11-14, 1999
• 12: B. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 49:291--307, 1970.
• 13: G. Kiczales, J. Lamping, A. Menhdhekar, C. Maeda, C. Lopes, J.-M. Loingtier, and J. Irwin. Aspect-oriented programming. In ECOOP '97, pages 220--242. June 1997.
• 14: K. McAloon and C. Tretkoff. 2LP: Linear Programming and Logic Programming. In V. Saraswat and P. V. Hentenryck, editors, Principles and Practice of Constraint Programming. The MIT Press, Cambridge, Ma, 1995.
• 15: Laurent Michel , Pascal Van Hentenryck, Localizer: a Modeling Language for Local Search, INFORMS Journal on Computing, v.11 n.1, p.1-14, January 1999 [doi>10.1287/ijoc.11.1.1]
• 16: Laurent Michel , Pascal Van Hentenryck, Localizer, Constraints, v.5 n.1-2, p.43-84, January 2000 [doi>10.1023/A:1009818401322]
• 17: S. Minton, M. Johnston, and A. Philips. Solving Large-Scale Constraint Satisfaction and Scheduling Problems using a Heuristic Repair Method. In AAAI-90, August 1990.
• 18: A. Nareyek. Constraint-Based Agents. Springer Verlag, 1998.
• 19: Robert Paige , Shaye Koenig, Finite Differencing of Computable Expressions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.402-454, July 1982 [doi>10.1145/357172.357177]
• 20: Bruce D. Parrello , Waldo C. Kabat , L. Wos, Job-shop scheduling using automated reasoning: a case study of the car-sequencing problem, Journal of Automated Reasoning, v.2 n.1, p.1-42, 1986
• 21: Ganesan Ramalingam, Bounded incremental computation, University of Wisconsin at Madison, Madison, WI, 1993
• 22: A. Schaerf, M. Lenzerini, and M. Cadoli. Local++: A c++ framework for local search algorithms. Technical Report 11-99, Dipartimento di Informatica e Sistemistica, Universita di Roma, La Sapienza, May 1999.
• 23: Bart Selman , Henry A. Kautz , Bram Cohen, Noise strategies for improving local search, Proceedings of the twelfth national conference on Artificial intelligence (vol. 1), p.337-343, October 1994, Seattle, Washington, United States
• 24: Ivan Edward Sutherland, Sketchpad: A man-machine graphical communication system (Outstanding dissertations in the computer sciences), Garland Publishing, Inc., New York, NY, 1980
• 25: Pascal Van Hentenryck, Constraint satisfaction in logic programming, MIT Press, Cambridge, MA, 1989
• 26: Pascal Van Hentenryck, The OPL optimization programming language, MIT Press, Cambridge, MA, 1999
• 27: P. Van Hentenryck and Y. Deville. The Cardinality Operator: A New Logical Connective and its Application to Constraint Logic Programming. In ICLP-91, June 1991.
• 28: J. Walser. Integer Optimization by Local Search. Springer Verlag, 1998.
• 29: D. Yellin , R. Strom, INC: a language for incremental computations, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.115-124, June 20-24, 1988, Atlanta, Georgia, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.5 Object-oriented Programming

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.13 Reusable Software
            Subjects: Reusable libraries; Reuse models
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Constraints; Frameworks
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Algorithms, Experimentation, Languages

Keywords:
constraint, incrementality, local search, optimization