Constraint Programming
Constraint programming (CP) is an technique of ever growing importance for solving hard combinatorial problems. When representing a problem as a set of variables to which we need to assign values from some finite domain so that a set of constraints is satisfied, the core algorithmic task of CP consists in "constraint filtering": Each constraint is considered sequentially, and it is determined which values a variable cannot possibly take (and can therefore be removed from the variable's domain) given that the constraint must be satisfied and that the other variables can only take values from their (remaining) domains.
Project status: Active
People
| Meinolf Sellmann |
Publications
Aron, I., Leventhal, D., and Sellmann, M. A Totally Unimodular Description of the Consistent Value Polytope for Binary CSPs. In Proceedings of the Third International Conference on Integration of AI and OR Techniques (CP-AI-OR) (2006), Springer Verlag, pp. 16-28. [ pdf ]
Flener, P., Pearson, J., Sellmann, M., and Van Hentenryck, P. Static and Dynamic Structural Symmetry Breaking. In Proceedings of the Twelfth International Conference on Principles and Practice of Constraint Programming (CP) (Nantes, France, Sep 2006), Springer, pp. 695-699. [ pdf ]
Sellmann, M. The Theory of Grammar Constraints. In Proceedings of the Twelfth International Conference on Principles and Practice of Constraint Programming (CP) (2006), Springer, pp. 530-544. [ pdf ]
Gellermann, T., Sellmann, M., and Wright, R. Shorter Path Constraints for the Resource Constrained Shortest Path Problem. In Proceedings of the Second International Conference on the Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization (CPAIOR) (2005), Springer, pp. 201-216. [ postscript | pdf ]
Katriel, I., Michel, L., and Van Hentenryck, P. Maintaining Longest Paths Incrementally. Constraints 10, 2 (Apr 2005), 159-183. [ pdf ]
Sellmann, M. Approximated Consistency for the Automatic Recording Constraint. In Proceedings of the Eleventh International Conference on Principles and Practice of Constraint Programming (CP) (2005), Springer, pp. 822-826. [ postscript | pdf ]
Sellmann, M., and Hentenryck, P. V. Structural Symmetry Breaking. In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI) (2005), pp. 298-303. [ postscript | pdf ]
Van Hentenryck, P. Introduction to the Special Issue on Principles and Practice of Constraint Programming. Constraints 10, 1 (Jan 2005). [ pdf ]
Gomes, C., Sellmann, M., van Es, C., and van Es, H. The Challenge of Generating Spatially Balanced Scientific Experiment Designs. In Proceedings of the First International Conference on the Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR) (2004), Springer, pp. 387-394. [ postscript | pdf ]
Gomes, C., and Sellmann, M. Streamlined Constraint Reasoning. In Proceedings of the Tenth International Conference on the Principles and Practice of Constraint Programming (CP) (2004), Springer, pp. 274-287. [ postscript | pdf ]
Michel, L., and Van Hentenryck, P. A Decomposition-Based Implementation of Search Strategies. ACM Transactions on Computational Logic 5, 2 (2004), 351-383. [ pdf ]
Michel, L., and Van Hentenryck, P. Iterative Relaxations for Iterative Flattening in Cumulative Scheduling. In Proceedings of the 14th International Conference on Automated Planning and Scheduling (Whistler, British Columbia, Canada, Jun 2004), pp. 200-208. [ pdf ]
Sellmann, M. The Practice of Approximated Consistency for Knapsack Constraints. In Proceedings of the Nineteenth National Conference on Artificial Intelligence (AAAI) (2004), AAAI Press, pp. 179-184. [ postscript | pdf ]
Sellmann, M. Theoretical Foundations of CP-based Largrangian Relaxation. In Proceedings of the Tenth International Conference on the Principles and Practice of Constraint Programming (CP) (2004), Springer, pp. 634-647. [ postscript | pdf ]
Van Hentenryck, P., and Michel, L. Constraint Languages for Combinatorial Optimizations. In Operations Research and Technology: Tutorials from INFORMS 2004. Kluwer Academic Publishers, 2004.
Bessiere, C., and Van Hentenryck, P. To Be or Not to Be...a Global Constraint. In Proceedings of the International Conference on Constraint Programming (CP-2003) (Kinsale, Ireland, Sep 2003), pp. 789-794. [ pdf ]
Michel, L., and Van Hentenryck, P. Maintaining Longest Paths Incrementally. In Proceedings of the 9th International Conference on Constraint Programming (CP-2003) (Kinsale, Ireland, Sep 2003), pp. 540-554. [ pdf ]
Sellmann, M. Approximated Consistency for Knapsack Constraints. In Proceedings of the Ninth International Conference on the Principles and Practices of Contraint Programming (CP) (2003), Springer, pp. 679-693. [ postscript | pdf ]
Sellmann, M. Cost-Based Filtering for Shorter Path Constraints. In Proceedings of the Ninth International Conference on the Principles and Practices of Contraint Programming (CP) (2003), Springer, pp. 694-708. [ postscript | pdf ]
Sellmann, M., and Fahle, T. Constraint Programming Based Lagrangian Relaxation for the Automatic Recording Problem. Annals of Operations Research (AOR) 118 (2003), 17-33. [ postscript | pdf ]
Van Hentenryck, P., Michel, L., Paulin, F., and Puget, J. The OPL Studio Modeling System. In Modeling Languages in Mathematical Optimization. Kluwer Academic Publishers, 2003.
Van Hentenryck, P., Agren, M., Flener, P., and Pearson, J. Tractable Symmetry Breaking for CSPs with Interchangeable Values. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI'03) (Acapulco, Mexico, 2003), pp. 277-284. [ pdf ]
Fahle, T., and Sellmann, M. Cost-Based Filtering for the Constrained Knapsack Problem. Annals of Operations Research (AOR) 115 (2002), 73-93. [ postscript | pdf ]
Fahle, T., Junker, U., Karisch, S. E., Kohl, N., Sellmann, M., and Vaaben, B. Constraint Programming Based Column Generation for Crew Assignment. Journal of Heuristics (JOH), Kluwer Academic Publishers 8, 1 (2002), 59-81. [ postscript | pdf ]
Sellmann, M. An Arc-Consistency Algorithm for the Minimum Weight All Different Constraint. In Proceedings of the Eighth International Conference on the Principles and Practice of Constraint Programming (CP) (2002), Springer. [ postscript | pdf ]
Sellmann, M., Zervoudakis, K., Stamatopoulos, P., and Fahle, T. Crew Assignment via Constraint Programming: Integrating Column Generation and Heuristic Tree Search. Annals of Operations Research (AOR) 115 (2002), 207-225. [ postscript | pdf ]
Sellmann, M., and Harvey, W. Heuristic Constraint Propagation. In Proceedings of the Eighth International Conference on the Principles and Practice of Constraint Programming (CP) (2002), Springer, pp. 738-743. [ postscript | pdf ]
Sellmann, M. Reduction Techniques in Constraint Programming and Combinatorial Optimization. PhD thesis, University of Paderborn, 2002.
Van Hentenryck, P. Constraint and Integer Programming in OPL. Informs Journal on Computing 14, 4 (2002), 345-372.
Van Hentenryck, P., and Michel, L. The Modeling Language OPL: A Short Overview. In Optimization Software Class Libraries. Kluwar Academic Publishers, 2002.
Benhamou, F., and Van Hentenryck, P. In Honor of Alain Colmerauer's 60th Birthday. Theory and Practice of Logic Programming 1, 6 (Nov 2001).
Fahle, T., Schamberger, S., and Sellmann, M. Symmetry Breaking. In Proceedings of the Seventh International Conference on the Principles and Practice of Constraint Programming (CP) (2001), Springer, pp. 93-107. [ postscript | pdf ]
Michel, L., and Van Hentenryck, P. Modeler++:A Modeling Layer for Constraint Programming. In Proceedings of the Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CP'AI'OR'2001) (Ashford, England, Apr 2001). [ pdf ]
Sellmann, M., and Fahle, T. Coupling Variable Fixing Algorithms for the Automatic Recording Problem. In Proceedings of the Ninth Annual European Symposium on Algorithms (ESA) (2001), Springer, pp. 134-145. [ postscript ]
Ramachandran, V., Van Hentenryck, P., and Cortesi, A. Abstract Domains for Reordering CLP (Rlin) Programs. Journal of Logic Programming 42 (2000), 217-256.
Van Hentenryck, P., and Michel, L. OPL Script: Composing and Controlling Models. In New Trends in Constraints, Lecture Notes in Artificial Intelligence (LNAI 1865). Springer Verlag, 2000. [ pdf ]
Van Hentenryck, P. A Preview of OPL. In Proceedings of the International Conference on Practical Applications of Constraint and Logic Programming (Manchester (UK), Apr 2000). [ pdf ]
Van Hentenryck, P. Programmation par Contraintes. Techniques et Sciences Informatiques 19 (Jan 2000), 1-6.
Van Hentenryck, P., Perron, L., and Puget, J.-F. Search and Strategies in OPL. ACM Transactions on Computational Logic 1, 2 (Oct 2000), 285-320. [ pdf ]
Junker, U., Karisch, S. E., Kohl, N., Vaaben, B., Fahle, T., and Sellmann, M. A Framework for Constraint Programming Based Column Generation. In Proceedings of the Fifth International Conference on the Principles and Practice of Constraint Programming (CP) (1999), Springer, pp. 261-274. [ pdf ]
Van Hentenryck, P., Michel, L., Laborie, P., Nuijten, W., and Rogerie, J. Combinatorial Optimization in OPL Studio. In Proceedings of the 9th Portugese Conference on Artificial Intelligence (EPIA'99) (Evora (Portugal), Sep 1999), pp. 1-15. [ pdf ]
Van Hentenryck, P., Michel, L., Perron, L., and Regin, J. Constraint Programming in OPL. In Proceedings of the International Conference on Principles and Practice of Declarative Programming (PPDP'99) (Paris (France), Sep 1999), pp. 98-116. [ pdf ]
Van Hentenryck, P. OPL: A Modeling Language for Combinatorial Optimization. MIT Press, 1999.
Van Hentenryck, P., and Michel, L. OPL Script: Composing and Controlling Models. In Proceedings of the European Research Consortium for Informatics and Mathematics (ERCIM) Workshop on New Trends in Constraints (Paphos, Cyprus, Oct 1999), pp. 75-90. [ pdf ]
Van Hentenryck, P., Saraswat, V., and Deville, Y. The Design, Implementation, and Evaluation of the Constraint Language cc(FD). The Journal of Logic Programming 37 (1998), 139-164. [ pdf ]
Van Hentenryck, P. Constraint Programming. In Encyclopedia of Science and Technology. Marcel Dekker, 1997.
Van Hentenryck, P. Constraint Programming for Combinatorial Search. Constraints 2 (Apr 1997), 99-101.
Van Hentenryck, P., and Saraswat, V. Constraint Programming: Strategic Directions. Constraints 2 (Apr 1997), 7-34. [ pdf ]
Imbert, J.-L., and Van Hentenryck, P. Redundancy Elimination with a Lexicographic Solved Form. Annals of Mathematics and Artifical Intelligence 17 (1996), 85-106. [ pdf ]
Refalo, P., and Van Hentenryck, P. CLP(/cal Rlin) Revised. In Proceedings of the Joint International Conference and Symposium on Logic Programming (JICSLP'96) (Bonn, Sep 1996), pp. 22-36.
Ramachandran, V., and Van Hentenryck, P. LSign Reordered. In Proceedings of the Static Analysis Symposium (SAS-95) (Glasgow, UK, Sep 1995), pp. 330-347.
Van Hentenryck, P., and Ramachandran, V. Backtracking without Trailing in CLP. ACM Transactions on Programming Languages and Systems 17 (Jul 1995), 635-671. [ pdf ]
Van Hentenryck, P. Constraint Solving for Combinatorial Search Problems: A Tutorial. In Proceedings of the First Conference on Principles and Practice of Constraint Programming (CP'95) (Cassis, France, Sep 1995), pp. 564-587.
Van Hentenryck, P., Saraswat, V., and Deville, Y. The Design, Implementation, and Evaluation of the Constraint Language cc(FD). In Constraint Programming: Basics and Trends. Springer Verlag, 1995.
Benhamou, F., McAllester, D., and Van Hentenryck, P. CLP(Intervals) Revisited. In Proceedings of the International Logic Programming Symposium (ILPS-94) (Ithaca, NY, Nov 1994), pp. 124-138. [ pdf ]
Van Hentenryck, P., and Ramachandran, V. Backtracking without Trailing in CLP(/cal Rlin). In Proceedings of the ACM-SIGPLAN Conference on Programming Language Design and Implementation (PLDI-94) (Orlando, FL, Jun 1994).
Van Hentenryck, P. Scheduling and Packing in the Constraint Language of cc(FD). In Intelligent Scheduling. Morgan Kaufman, 1994.
Imbert, J., and Van Hentenryck, P. Efficient Handling of Disequations in CLP Over Linear Rational Arithmetics. In Constraint Logic Programming: Selected Research. MIT Press, 1993.
Ramachandran, V., and Van Hentenryck, P. Incremental Algorithms for Constraint Solving and Entailment over Rational Trees. In Proceedings of the 13th Conference on Foundations of Software Technology and Theoretical Computer Science (Bombay, India, Dec 1993), pp. 205-217.
Van Hentenryck, P., and Deville, Y. The Cardinality Operator: A New Logical Connective and its Application to Constraint Logic Programming. In Constraint Logic Programming: Selected Research. MIT Press, 1993.
Deville, Y., and Van Hentenryck, P. Construction of CLP Programs. In Logic Programming: New Frontiers. Kluwar Academic Publishers, 1992.
Dincbas, M., Simonis, H., and Van Hentenryck, P. Solving a Cutting-Stock Problem with the Constraint Logic Programming Language CHIP. Mathl. Comput. Modeling 16 (1992), 95-105.
Van Hentenryck, P. Constraint Logic Programming. In Encyclopedia of Artificial Intelligence (Second Edition). Wiley, 1992.
Van Hentenryck, P., Simonis, H., and Dincbas, M. Constraint Satisfaction using Constraint Logic Programming. Artificial Intelligence 58 (1992), 113-159. [ pdf ]
Van Hentenryck, P., and Graf, T. Standard Forms for Rational Linear Arithmetics in Constraint Logic Programming. Annals of Mathematics and Artificial Intelligence 5, 2-4 (1992), 303-319.
Van Hentenryck, P. The CLP Language CHIP: Constraint Solving and Applications. In Proceedings of the IEEE Computer Society International Conference (COMPCON) (San Francisco, CA, Feb 1991).
Van Hentenryck, P. Constraint Logic Programming. Knowledge Engineering Review 6 (1991), 151-194.
Van Hentenryck, P., and Deville, Y. The Cardinality Operator: A New Logical Connective and its Application to Constraint Logic Programming. In Proceedings of the Eighth International Conference on Logic Programming (ICLP-91) (1991), pp. 745-759.
Van Hentenryck, P., and Provost, T. L. Incremental Search in Constraint Logic Programming. New Generation Computing, 1991: Special Issue on selected papers from ICLP-90 9, 3/4 (1991), 257-276.
Van Hentenryck, P., and Deville, Y. Operational Semantics of Constraint Logic Programming over Finite Domains. In Proceedings of the Third International Symposium on Programming Language Implementation and Logic Programming (PLILP-91) (Passau, Germany, Aug 1991), pp. 395-406.
Dincbas, M., Simonis, H., and Van Hentenryck, P. Solving Large Combinatorial Problems in Logic Programming. Journal of Logic Programming 8 (1990), 75-93.
Graf, T., Van Hentenryck, P., c. Pradelles, and Zimmer, L. Simulation of Hybrid Circuits in Constraint Logic Programming. Computers and Mathematics with Applications 20 (1990), 45-56.
Van Hentenryck, P. Incremental Constraint Satisfaction in Logic Programming. In Proceedings of the Seventh International Conference on Logic Programming (ICLP-90) (Jerusalem, Israel, Jun 1990), pp. 189-202.
Van Hentenryck, P. A Logic Language for Combinatorial Optimization. Annals of Operations Research 21 (1990), 247-274.
Van Hentenryck, P., and Graf, T. Standard Forms for Rational Linear Arithmetics in Constraint Logic Programming. In Proceedings of the International Symposium on Artificial Intelligence and Mathematics (Fort Lauderdale, FL, Jan 1990).
Dincbas, M., Simonis, H., and Van Hentenryck, P. Extending Equation Solving and Constraint Handling in Logic Programming. In Resolution of Equations in Algebraic Structures. Academic Press, 1989.
Graf, T., Van Hentenryck, P., Pradelles, C., and Zimmer, L. Simulation of Hybrid Circuits in Constraint Logic Programming. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-89) (Detroit, MI, Aug 1989), pp. 72-77.
Van Hentenryck, P. Constraint Satisfaction in Logic Programming. MIT Press, 1989.
Van Hentenryck, P. Parallel Constraint Satisfaction in Logic Programming: Preliminary Results of CHIP within PEPSys. In Proceedings of the Sixth International Conference on Logic Programming (ICLP-89) (Lisbon, Portugal, Jun 1989), pp. 165-180.
Dincbas, M., Van Hentenryck, P., Simonis, H., Aggoun, A., and t. Graf. Applications of CHIP to Industrial and Engineering Problems. In Proceedings of the First International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems (Tullahoma, TN, Jun 1988), pp. 885-892.
Dincbas, M., Simonis, H., and Van Hentenryck, P. Solving the Car Sequencing Problem in Constraint Logic Programming. In Proceedings of the European Conference on Artificial Intelligence (ECAI-88) (Munich, Aug 1988), pp. 42-58.
Dincbas, M., Simonis, H., and Van Hentenryck, P. Solving a Cutting-Stock Problem in Constraint Logic Programming. In Proceedings of the Fifth International Conference on Logic Programming (ICLP-88) (Seattle, WA, Aug 1988), pp. 42-58.
Dincbas, M., Simonis, H., and Van Hentenryck, P. Solving Large Scheduling Problems in Logic Programming. In Proceedings of the Joint International Conference on Operations Research and Management Science (EURO-TIMS) (Paris, France, Jul 1988).
Van Hentenryck, P., and Carillon, J.-P. Generality versus Specificity: an Experience with AI and OR Techniques. In Proceedings of the American Association for Artificial Intelligence (AAAI-88) (St. Paul, MN, Aug 1988).
Dincbas, M., Simonis, H., and Van Hentenryck, P. Extending Equation Solving and Constraint Handling in Logic Programming. In Proceedings of the Colloquium on Resolution of Equations in Algebraic Structures (CREAS), MCC (Austin, TX, May 1987).
Van Hentenryck, P., and Dincbas, M. Forward Checking in Logic Programming. In Proceedings of the Fourth International Conference on Logic Programming (ICLP-87) (Melbourne, Australia, May 1987), pp. 229-256.
Van Hentenryck, P. A Framework for Consistency Techniques in Logic Programming. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-87) (Milan, Italy, Aug 1987), pp. 2-8.
Van Hentenryck, P., and Dincbas, M. Domains in Logic Programming. In Proceedings of the American Association for Artificial Intelligence Conference (AAAI-86) (Philadelphia, PA, Aug 1986), pp. 759-765.
| Page Owner: Webmaster | Last Modified: Mon Oct 23 14:57:09 2006 |