Pascal Van Hentenryck
Skip Abstract Section
Abstract
OPL is a modeling language for mathematical programming and combinatorial optimization. It is the first language to combine high-level algebraic and set notations from mathematical modeling languages with a rich constraint language and the ability to specify search procedures and strategies that are the essence of constraint programming. This paper describes the facilities available in OPL to specify search procedures. It describes the abstractions of OPL to specify both the search tree (search) and how to explore it (strategies). The paper also illustrates how to use these high-level constructs to implement traditional search procedures in constraint programming and scheduling.
- APT, K., BRUNEKREEF, J., PARTINGTON,V.,AND SCHAERF, A. 1998. Alma-O: An Imperative Language that Supports Declarative Programming. ACM Transactions on Programming Languages and Systems 20, 5 (September), 1014-1066.]] Google Scholar
Digital Library
- APT,K.AND SCHAERF, A. 1997. Search and Imperative Programming. In Proc. 24th Annual SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'97) (January 1997), pp. 67-79. ACM Press.]] Google ScholarDigital Library
- BISSCHOP,J.AND MEERAUS, A. 1982. On the Development of a General Algebraic Modeling System in a Strategic Planning Environment. Mathematical Programming Study 20, 1-29.]]Google ScholarCross Ref
- BOROVANSKY, P., KIRCHNER, C., KIRCHNER, H., MOREAU,P.,AND RINGEISSEN, C. 1998. An Overview of Elan. In Proceedings of the 2nd International Workshop on Rewriting Logic and its Applications (Pont-A-Mousson, France, September 1998).]]Google ScholarCross Ref
- CARLIER,J.AND PINSON, E. 1990. A Practical Use of Jackson's Preemptive Schedule for Solving the Job-Shop Problem. Annals of Operations Research 26, 269-287.]] Google ScholarDigital Library
- CHENG, B., LEE, J., LEUNG, H., AND LEUNG, Y. 1996. Speeding up Constraint Propagation by Redundant Modeling. In Proceedings of the Second International Conference on Principles and Practice of Constraint Programming (CP'96) (Cambridge, MA, August 1996). Springer Verlag.]]Google ScholarDigital Library
- COLMERAUER, A. 1990. An Introduction to Prolog III. Commun. ACM 28, 4, 412-418.]] Google ScholarDigital Library
- COLMERAUER, A. 1996. Sp~cification de Prolog IV. Technical report, Laboratoire d'informatique de Marseille.]]Google Scholar
- DEMEULESMEESTER,E.AND HERROELEN, W. 1992. A Branch and Bound Procedure for the Multiple Resource-Constrained Project Scheduling Problem. Management Science 38, 1803-1818.]]Google ScholarCross Ref
- DINCBAS, M., SIMONIS, H., AND VAN HENTENRYCK, P. 1988. Solving a Cutting-Stock Problem in Constraint Logic Programming. In Fifth International Conference on Logic Programming (Seattle, WA, August 1988).]]Google Scholar
- DINCBAS, M., VAN HENTENRYCK, P., SIMONIS, H., AGGOUN, A., GRAF,T.,AND BERTHIER, F. 1988. The Constraint Logic Programming Language CHIP. In Proceedings of the International Conference on Fifth Generation Computer Systems (Tokyo, Japan, December 1988).]]Google Scholar
- FOURER, R., GAY,D.,AND KERNIGHAN, B. 1993. AMPL: A Modeling Language for Mathematical Programming. The Scientific Press, San Francisco, CA.]]Google Scholar
- HARVEY,W.AND GINSBERG, M. 1995. Limited Discrepancy Search. In Proceedings of the 14th International Joint Conference on Artificial Intelligence (Montreal, Canada, August 1995).]]Google ScholarDigital Library
- ILOG OPL STUDIO 3.0. 2000. Reference Manual. Ilog SA, Gentilly, France.]]Google Scholar
- ILOG SOLVER 4.4. 1998. Reference Manual. Ilog SA, Gentilly, France.]]Google Scholar
- JAFFAR, J., MICHAYLOV, S., STUCKEY,P.,AND YAP, R. 1992. The CLP( < ) Language and System. ACM Trans. on Programming Languages and Systems 14, 3, 339-395.]] Google ScholarDigital Library
- LABURTHE,F.AND CASEAU, Y. 1998. SALSA: A Language for Search Algorithms. In Fourth International Conference on the Principles and Practice of Constraint Programming (CP'98) (Pisa, Italy, October 1998).]] Google ScholarDigital Library
- MAHER, M. 1987. Logic Semantics for a Class of Committed-Choice Programs. In Fourth International Conference on Logic Programming (Melbourne, Australia, May 1987), pp. 858-876.]]Google Scholar
- MARTIN,D.AND SHMOYS, P. 1996. A Time-based Approach to the Job-Shop Problem. In Proc. of 5th International Conference on Integer Programming and Combinatorial Optimization (IPCO'96) (Vancouver, Canada, 1996). Springer Verlag.]]Google ScholarCross Ref
- MCALOON,K.AND TRETKOFF, C. 1995. 2LP: Linear Programming and Logic Programming. In V. SARASWAT AND P. V. HENTENRYCK Eds., Principles and Practice of Constraint Programming. Cambridge, Ma: The MIT Press.]]Google Scholar
- PERRON, L. 1999. Search Procedures and Parallelism in Constraint Programming. In Fifth International Conference on the Principles and Practice of Constraint Programming (CP'99) (Alexandra, VA, October 1999).]] Google ScholarDigital Library
- PUGET, J.-F. 1994. A C++ Implementation of CLP. In Proceedings of SPICIS'94 (Singapore, November 1994).]]Google Scholar
- ROSEAUX. 1985. Programmation lin~aire et extensions; probl~mes classiques, Volume 3 of Exercices et probl~mes r~solus de Recherche Op~rationnelle. Masson, Paris.]]Google Scholar
- SARASWAT, V. 1993. Concurrent Constraint Programming. ACM Doctoral Dissertation Awards: Logic Programming. The MIT Press, Cambridge, MA.]] Google ScholarDigital Library
- SAVELBERGH, M. 1994. Preprocessing and Probing for Mixed Integer Programming Problems. ORSA Journal of Computing 6, 445-454.]]Google ScholarCross Ref
- SCHULTE, C. 1997. Programming Constraint Inference Engines. In Proceedings of the Third International Conference on Principles and Practice of Constraint Programming, Volume 1330 (Schloss Hagenberg, Linz, Austria, October 1997), pp. 519-533. Springer-Verlag.]]Google ScholarDigital Library
- SCHULTE, C. 2000. Programming Deep Concurrent Constraint Combinators. In Proceedings of the Second International Workshop on Practical Aspects of Declarative Languages (PADL'00), Volume 1753 (Boston, MA, January 2000). Springer-Verlag.]] Google ScholarDigital Library
- SMOLKA, G. 1995. The Oz Programming Model. In J. VAN LEEUWEN Ed., Computer Science Today. LNCS, No. 1000, Springer Verlag.]] Google ScholarDigital Library
- VAN HENTENRYCK, P. 1989. Constraint Satisfaction in Logic Programming. Logic Programming Series, The MIT Press, Cambridge, MA.]] Google ScholarDigital Library
- VAN HENTENRYCK, P. 1997. Visual Solver: A Modeling Language for Constraint Programming. In Third International Conference on the Principles and Practice of Constraint Programming (CP'97) (Lintz, Austria, October 1997). (Invited Talk).]]Google Scholar
- VAN HENTENRYCK, P. 1999. The OPL Optimization Programming Language. The MIT Press, Cambridge, Mass.]] Google ScholarDigital Library
- VAN HENTENRYCK,P.AND DEVILLE, Y. 1991. The Cardinality Operator: A New Logical Connective and its Application to Constraint Logic Programming. In Eighth International Conference on Logic Programming (ICLP-91) (Paris (France), June 1991).]]Google Scholar
- VAN HENTENRYCK, P., MICHEL, L., LABORIE, P., NUIJTEN,W.,AND ROGERIE, J. 1999. Combinatorial Optimization in OPL Studio. In Proceedings of the 9th Portuguese Conference on Artificial Intelligence International Conference (EPIA'99) (Evora, Portugal, September 1999). (Invited Paper).]] Google ScholarDigital Library
- VAN HENTENRYCK, P., MICHEL, L., PERRON, L., AND REGIN, J. 1999. Constraint Programming in OPL. In Proceedings of the International Conference on the Principles and Practice of Declarative Programming (PPDP'99) (Paris, France, September 1999). (Invited Paper).]] Google ScholarDigital Library
Index Terms
- Search and strategies in OPL
Recommendations
Search by constraint propagation
PPDP '15: Proceedings of the 17th International Symposium on Principles and Practice of Declarative ProgrammingConstraint programming is traditionally presented as the combination of two components: a constraint model and a search procedure. In this paper we show that tree search procedures can be fully internalized in the constraint model with a fixed ...
A decomposition-based implementation of search strategies
Search strategies, that is, strategies that describe how to explore search trees, have raised much interest for constraint satisfaction in recent years. In particular, limited discrepancy search and its variations have been shown to achieve significant ...
A small embedding of logic programming with a simple complete search
DLS '16We present a straightforward, call-by-value embedding of a small logic programming language with a simple complete search. We construct the entire language in 54 lines of Racket---half of which implement unification. We then layer over it, in 43 lines, ...
Comments