What is constraint programming technology?
Constraint programming technology is used to find solutions to scheduling and combinatorial optimization problems. It is based primarily on computer science fundamentals, such as logic programming and graph theory, in contrast to mathematical programming, which is based on numerical linear algebra.
Constraint programming is invaluable when dealing with the complexity of many real-world sequencing and scheduling problems. Whether the problem at hand is to schedule people, machines or jobs of processes, you need constraint programming when there are complex logical and arithmetic relationships between decision variables, activities and resources.
A constraint programming model is expressed in a declarative fashion, using decision variables, constraints and objectives that must be minimized or maximized, just as in mathematical programming; Lexicographical multi-criteria objectives are possible in ILOG CPLEX CP Optimizer. IBM’s OPL modeling language and integrated development environment (IDE) and ILOG Concert Technology interfaces, also part of IBM ILOG CPLEX Optimization Studio, can be used to formulate constraint programming models as well as mathematical programming models. This gives the option to combine the technologies in a multi-model framework. For example, constraint programming can be used as a heuristic to find solutions for mixed integer programs.
Constraint programming looks first to reduce the set of possible values of the decision variables which will satisfy all the constraints using logical, graph-theoretic, arithmetic and other arguments. Once the deduction that some values from the decision variable’s domain are not possible, this information is propagated through the constraints perhaps enabling further deductions. Various search strategies are also used until a value is assigned to every decision variable, that is, until a solution is found. Once a first solution is found, the search proceeds to find further solutions with better objective values.
The power of modeling in constraint programming
Modeling in constraint programming revolves around the details of what is possible. For example, if you have to schedule a large number of resources and activities that respect capacity limitations, operational sequencing requirements, and business policies while meeting individual customer service goals, these modeling features are available to you:
Expression on interval properties
Finite capacity reservoir and resources
Set-up times and batches
These modeling features can be used for combinatorial optimization problems
Arithmetic linear and non-linear constraints
Specialized constraints and expressions:
Compatibility and incompatibility constraints:
• Define possible assignments for arrays of decision variables. They can be used, for instance, to model allowed transitions in a sequencing problem.
The model-and-run constraint programming optimizer
Three concepts are fundamental to the way constraint programming generates workable schedules and solutions from such complexity:
These concepts are built into the model-and-run optimizer of ILOG CPLEX CP Optimizer but are also available to build a customized search. The optimizer
The optimizer is tested on an extensive library of models and the search engine can be tuned via parameters or callbacks.