NordConsNet: What Is Constraint Programming?
Constraint programming is a rather novel set of methods and tools for modelling and solving constraint (optimisation or decision) problems, and originates from computer science, with strong roots in artificial intelligence. Constraint problems arise in many application domains, such as scheduling, rostering, planning, configuration, control, design, biology, finance, transport, logistics, and so on. In such problems, decisions have to be made (that is, the values of unknowns have to be determined) so that some constraints are satisfied and, optionally, some cost/benefit is minimised/maximised. The number of candidate combinations of decisions is usually astronomical, hence naïve search or just fast computers are of no help. Constraint programming works in an orthogonal but complementary way to other optimisation technologies (such as ILP, MILP, SAT, etc). For many problems, constraint programming has been shown to be very effective, if not (vastly) superior to other approaches, while the converse or a tie occurs for other problems. Naturally, these approaches are currently converging.
The existence of constraint programming and its trade-off with other approaches are still little known, especially in application areas where the latter have gained a strong foothold. Opportunities for obtaining better solutions, for obtaining solutions faster, and/or for solving problem instances of unprecedented scale are being missed.
Constraint programming applies techniques from:
- Artificial Intelligence
- Combinatorics
- Computational Logic
- Concurrent Computation
- Database Management
- Discrete Mathematics
- Operations Research
- Programming Languages
- Symbolic Reasoning
- User Interfaces
- Visualisation
- ...
to application areas as diverse as:
- Configuration
- Design
- Logistics
- Molecular Biology
- Planning
- Scheduling
- Transport
- ...