Constraint programming effectively solves a group of problems after translating them into variables and constraints represented in a mathematical equation.
Several ways to solve a problem in computing exist. An example is brute-forcing or coming up with various ways to get to the solution (aka “guessing”). Another is constraint programming where one views the problem as limitations to get to the solution.
Other interesting terms…
Read More about “Constraint Programming”
Constraint programming can give a new perspective to solving difficult problems. While it may not work for every situation, it may present new ways to get to the desired solution. In a sense, it allows programmers to look at a problem from a different angle.
Let’s take the Pythagorean theorem to illustrate. In the theorem, the constraint is represented by the equation a2 + b2 = c2. It has three variables—a, b, and c—that each correspond to a domain or a nonnegative value. The program has to compute for the value of each variable using different domains to come up with the answer.
What Elements Comprise a Constraint Programming Problem?
These elements are present in any constraint problem:
- Constraint: The equation that represents the problem or simply, the problem statement. Three types of constraints exist, namely:
- Extensional: Defined by enumerating the set of values that would satisfy it.
- Arithmetic: Defined by an arithmetic expression such as equations that use <, >, ≤, ≥, =, ≠, and so on.
- Logical: Defined with an explicit semantic statement such as “AllDifferent,” “AtMost,” and others.
- Variables: The possible values that can fill in the equation to come up with answers.
- Domains: The nonnegative numbers that the variables can take. These can be of various types, including:
- Boolean: Only true/false constraints apply to these.
- Integer: Also known as “rational domains,” or all real numbers except those that cause the denominator to be equal to 0.
- Interval: Used particularly for scheduling problems.
- Linear: Only linear functions or equations that when turned into graphs result in a straight line are described and analyzed.
- Finite: Constraints are defined to only include finite sets. These are most commonly used.
- Mixed: Involves two or more of the above-mentioned types.
How Does Constraint Programming Work?
Take a look at this module in video format to see how basic constraint programming works.
Constraint programming equations can be turned into two problem types to find the solution:
1. Constraint satisfaction problem solving can help users:
- Find a solution that satisfies all the constraints
- Find all possible solutions to a problem
- Prove that the problem has no solution
2. Constraint optimization problem solving, meanwhile, can aid users in:
- Finding a solution that satisfies all the constraints
- Finding the best solution in line with the objective
- Proving that the best solution is the optimal one
- Proving that the problem cannot be solved
What Models Are Used in Constraint Programming?
Two models are commonly used in constraint programming:
- Refinement model: Variables are initially unassigned. Each variable can have any value within a given range or domain. As the computation progresses, values within the domain are taken out if they do not satisfy the constraint until a single number is found for each variable.
- Perturbation model: Variables get assigned the same initial value. At other times, one or more variables receive perturbations or changes to their old values. The system continues to assign new values to other variables until the solution is found.
—
You may not know it, but constraint programming, specifically the perturbation model, has a lot to do with spreadsheet applications.
