Constraint programming is set of algorithms that can help you to identify feasible solutions out of a very large set of possible values that satisfy all given constraints.
It relies on logic-based methods such as domain reduction and constraint propagation to accelerate the search by eliminating all the impossible solutions in an efficient way.
Main goal of CP is primary to find feasible solution,which does not necessarily have to be optimal, although CO can find the optimum solution as well.
Operational Research and Management Science was invented to help optimize business processes, and to use all available resources (people, machines, vehicles, money, risk, negotiations…) in an efficient manner.
CP is one of the many fields of Operational Research and Management Science.
It’s closely related with combinatorics, and is a perfect fit for cases where classical algorithms like LP / IP / MIP are not applicable (mainly in the area of NP hard problem types).
There are many practical examples of CP like scheduling, planning, routing problem and numerous other domains with heterogeneous constraints.
On the following link you can find out more about Operation Research:
https://www.josip-pojatina.com/en/introduction-to-operations-research/
In the following example I’ll create a very simple CP model in one of the Mathematical Modeling language.
Problem statement:
Find a three-digit number with the following constraints:
- First digit will be 1 (I named it x1 variable, although it’s constant)
- Second digit (x2) has to be different from the first digit
- sum of the first (x1) digit and the second (x2) digit must be divisible by 2 like: ( x1+ x2) mod 2 = 0
- Third digit (x3) has to be different from the first two digits
- sum of the first three digits must be divisible by 3 like: (x1 + x2 + x3) mod 3 = 0
This is how I apply Mathematical Modeling to solve the task.
using CP;
range r = 2..9;
int x1 = 1;
dvar int x2 in r;
dvar int x3 in r;
subject to {
x2 != x3;
(x1 + x2) mod 2 == 0;
(x1 + x2 + x3) mod 3 == 0;
}Summary:
Constraint Programming is one of the possible solution to solve many kind of problems that other algorithms like LP or MIP are unable to solve.
In the previous, example you can see what CP is all about.
In the future I’ll write about more realistic problems which can be efficiently solved by using algorithms from the Operational Research and Management Science to optimize business critical processes.
Comments