OPL CP Optimizer in a nutshell

Provides the basics of using constraint programming in an OPL model.

A CP model must be declared as such. It uses only discrete decision variables for which you must define a domain. The product of all domain sizes makes up the search space. CP models are further characterized by specific constraints and expressions, and parameterizable propagation, and search.

Here are the basics of using constraint programming in an OPL model. Read the CP Optimizer documentation for details.

  1. Declaration: A CP model must start with the statement

    using CP;

    Otherwise, it will be considered an MP model solved by the CPLEX engine.

  2. Decision variables: Use only discrete variables as decision variables.

  3. Decision expressions: It is possible to constrain floating point expressions, or to use them as an objective term. It is also possible to declare floating-point expressions with the dexpr keyword, as in the floatexpr.mod code sample.

  4. Domain definition: From OPL 5.2 onwards, you must define domains for your decision variables. CP does not work well with undefined domains.

  5. Search space: The search space is the product of all domain sizes, measured by its log (base 2). The search space is a measure of how difficult a problem is for the CP Optimizer engine. It is also a limit for the Preview Edition of CPLEX Optimization Studio.

    See the Glossary for a definition of search space..

  6. Constraints and expressions: Specific arithmetic, logical, temporal, and specialized constraints and expressions are supported by the CP Optimizer engine for CP combinatorial and scheduling models. See Constraints available in constraint programming in the Language Reference Manual.

  7. Parameters: You can set various parameters for propagation control, log control, search control, and so on. See Constraint programming options in Parameters and settings in OPL.

  8. Propagation: Constraints in CP model are propagated at execution time by the CP solving engine. Constraint propagation is the process of communicating the domain reduction of a decision variable to all of the constraints that are stated over this variable. This process can result in more domain reductions. These domain reductions, in turn, are communicated to the appropriate constraints. This process continues until no more variable domains can be reduced or when a domain becomes empty. In the latter case, an empty domain means that the model has no solution.

  9. Search: To find a solution, the CP Optimizer search functionality implicitly generates combinations of values for decision variables by means of constructive strategies. these strategies are executed and guided towards optimal solutions in order to converge rapidly. The CP Optimizer search uses a variety of guides and uses the most appropriated one depending on the model structure and on constraint propagation. The powerful default search gives satisfactory results in most cases but in specific cases, you can fine-tune search strategies.

  10. Search phases: The engine parameters modify the search behavior in a global way. The impact of the parameter is the same on all parts of the model. Sometimes, a useful knowledge of some part of the model can be used to modify how the search should be performed on a limited part of the model. In that case, search modifiers can be used to apply some kind of local search settings on this limited part. They are applied by specifying which modifiers are to be used on which variables at each phase. You can specify as many phases as you want.

    See Using IBM ILOG Script in constraint programming.