1. Introduction to constraint programming

In this chapter, we introduce Constraint Programming (CP) and the or-tools library and its core principles. We also present the content of this manual.

Overview:

This chapter is divided in three parts. First, we introduce Constraint Programming by looking at an example of the solving process of our CP solver in the section The 4-Queens Problem. We give a brief definition of Constraint Programming in the section What is constraint programming? and show some practical problems where CP stands out in the section Real examples. Second, we lay some practical and theoretical foundations for the whole manual. A little bit of theory in the section A little bit of theory provides some theoretical backgrounds with interesting practical implications. If you don’t know how to tackle a problem, we introduce a (very) simple strategy (the three-stage method in the section The three-stage method: describe, model and solve) that can help you when confronted with a problem to solve. This method will be applied repeatedly in this manual. Another recurrent idea in this manual is to be aware of tradeoffs. This idea is the key to successful optimization and well worth the whole section It’s always a matter of tradeoffs. Finally, we outline the general principles of the library in the section The Google or-tools library and detail the content of this manual in the section The content of the manual.

Prerequisites:

• None. Being open minded, relaxed and prepared to enjoy the or-tools library helps though.

Content:

• 1.1. The 4-Queens Problem
  • 1.1.1. The problem
  • 1.1.2. A mathematical translation of the problem
  • 1.1.3. Propagation and search
• 1.2. What is constraint programming?
  • 1.2.1. Strength of Constraint Programming
  • 1.2.2. The search
• 1.3. Real examples
  • 1.3.1. Success stories
  • 1.3.2. Can CP be compared to the holy grail of Operations Research?
• 1.4. A little bit of theory
  • 1.4.1. Constraint Satisfaction Problems (CSP) and Constraint Optimization Problems (COP)
  • 1.4.2. Problems, instances and solutions
  • 1.4.3. Complexity theory for the hurried reader
  • 1.4.4. Complexity theory in a few lines
• 1.5. The three-stage method: describe, model and solve
  • 1.5.1. Describe
  • 1.5.2. Model
  • 1.5.3. Solve
• 1.6. It’s always a matter of tradeoffs
• 1.7. The Google or-tools library
• 1.8. The content of the manual
  • 1.8.1. Part I: Basics
  • 1.8.2. Part II: Customization
  • 1.8.3. Part III: Routing
  • 1.8.4. Part IV: Technicalities
  • 1.8.5. Appendices
• 1.9. Summary