A Constraint Satisfaction Problem (CSP) is defined by a set of variables, each one with a domain of values, and a set of constraints defining the feasible combinations of values. Solving a CSP consists of assigning each variable a value in its domain such that all constraints are satisfied. It is then possible to add one or many optimization criteria. The term Constraint Programming (CP) comes from the fact that the problem is described in a declarative way through its constraints. It is a very nice programming paradigm where, instead of giving a procedure about how to solve the problem, the user simply specifies the list of properties that must hold in a solution: “Constraint programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming: the user states the problem, the computer solves it.” [Eugene C. Freuder, Constraints, April 1997]. This clear separation between the technical aspects and the functional aspects goes beyond programming. It is a different way of thinking that is highly valuable when talking to business representatives for industrial projects. Read more.
Once the CP model has been established, it can be solved using a generic CP solver, such as Choco Solver. Constraint filtering algorithms will remove infeasible values from the domains using logic and advanced algorithms, whereas search heuristics will explore the search space in a smart way. The solving process of a constraint-programming solver consists of alternating between filtering and search until finding a feasible solution or proving that none exist. This black-box approach is sufficient to solve many problems. However, in order to solve very hard problems, it is often necessary to implement dedicated filtering algorithm (for custom global constraints) and search heuristics. This task requires a strong expertise in Constraint-Programming and a deep knowledge of the solver. This is why our experts are here to support you.
Choco Solver is an Open Source Java library for Constraint Programming that has been used for more than 15 years by many companies and universities. Choco is among the most efficient solvers available and has a high code quality. Being a Java library, it can be integrated very easily to develop innovative web-services for decision making. Cosling develops Choco Solver together with École des Mines de Nantes.
Give a look at our tutorials to discover Choco Solver 4.0!