The search process

How to influence the default search of CP Optimizer.

Constraint programming techniques have been seen for a long time as harder to use than mathematical programming because it was sometimes necessary to define search procedures using complex syntaxes and concepts. Now the IBM® ILOG® CP Optimizer engine includes a powerful default search. This means that without giving any particular indication on how the solution or optimal solution is to be found, some combinations of techniques are used with default behaviors so that good solutions are quickly found for a wide variety of problems.

However, you can influence the search process by:

Changing CP parameters
Defining search phases

Changing CP parameters

You can change CP Optimizer parameters by means of script statements. See Changing CP parameters.

Setting limits

Limits are just a particular type of parameters you can change with a certain impact on the search process. You can set a limit on the number of failures during the search or on the time spent searching. Here are examples on how to change these parameters :


execute {
   cp.param.FailLimit = 500;
   cp.param.TimeLimit = 20;
}

Changing the search behavior

You can also change the search behavior by using CP parameters to change the nature of the search. The CP Optimizer engine includes several different methods to search for solutions. Some parameters enable you to decide which search method to use exactly. This is useful in some cases. The default search uses default combinations that are proven to be the best choice on average. However, better combinations can be found on particular cases. Here are examples on how to change such parameters:


execute {
   cp.param.searchType = "multiPoint";
   writeln("Search type is " + cp.param.searchType);
   cp.param.DefaultInferenceLevel = "Extended";
}

Defining search phases

Sometimes, the default search may not be capable of finding good enough values in an appropriate amount of time. By changing parameters, you can modify slightly how these default algorithms work. When this is not sufficient, you can also help the engine by providing some indications on the structure of the search space. The default search algorithm can use them efficiently to find good solutions. This is referred to as search phases.

For example, in the steel mill code sample, the preprocessing part indicates that the engine must start instantiating the where variables.

execute {
   var f = cp.factory;
   cp.setSearchPhases(f.searchPhase(where));
}

In each phase, you can use search modifiers to apply specific settings that will be local to the search phase. To this effect, you specify which ones are used on which variables at each phase.

The syntax to apply search modifiers in a phase is:


var phase1 = searchPhase(variable_array_from_model,
                               variable_selector,
                               value_selector);

You can have as many phases as you want. You tell the CP Optimizer engine the phases to use with the syntax:


cp.setSearchPhases(phase1, phase2);

See Using IBM ILOG Script in constraint programming and Understanding solving statistics and progress (CP models).