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
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, Sept. 2006), Springer, pp. 695-699. [ pdf ]
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 ]
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 ]
Katriel, I., Michel, L., and Van Hentenryck, P. Maintaining Longest Paths Incrementally. Constraints 10, 2 (Apr. 2005), 159-183. [ 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 ]
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 ]
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, June 2004), pp. 200-208. [ 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 ]
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, Sept. 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, Sept. 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).
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 ]
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 ]
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 ]
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 ]
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 ]
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. Programmation par Contraintes. Techniques et Sciences Informatiques 19 (Jan. 2000), 1-6.
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., 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), Sept. 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), Sept. 1999), pp. 98-116. [ 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. OPL: A Modeling Language for Combinatorial Optimization. MIT Press, 1999.
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 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 ]
Van Hentenryck, P. Constraint Programming. In Encyclopedia of Science and Technology. Marcel Dekker, 1997.
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, Sept. 1996), pp. 22-36.
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 ]
Ramachandran, V., and Van Hentenryck, P. LSign Reordered. In Proceedings of the Static Analysis Symposium (SAS-95) (Glasgow, UK, Sept. 1995), pp. 330-347.
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, Sept. 1995), pp. 564-587.
Van Hentenryck, P., and Ramachandran, V. Backtracking without Trailing in CLP. ACM Transactions on Programming Languages and Systems 17 (July 1995), 635-671. [ pdf ]
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, June 1994).
Van Hentenryck, P. Scheduling and Packing in the Constraint Language of cc(FD). In Intelligent Scheduling. Morgan Kaufman, 1994.
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.
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.
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., 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.
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. Incremental Constraint Satisfaction in Logic Programming. In Proceedings of the Seventh International Conference on Logic Programming (ICLP-90) (Jerusalem, Israel, June 1990), pp. 189-202.
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. 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).
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. 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, June 1989), pp. 165-180.
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.
Van Hentenryck, P. Constraint Satisfaction in Logic Programming. MIT Press, 1989.
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.
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. Solving Large Scheduling Problems in Logic Programming. In Proceedings of the Joint International Conference on Operations Research and Management Science (EURO-TIMS) (Paris, France, July 1988).
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, June 1988), pp. 885-892.
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.
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., 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 |