Setting parameters on search

Parameters can be set on the search to limit the search as well as adjust the tolerance on optimality.

Search parameterization is an important feature of CP Optimizer. One use of parameters is to limit the search. The parameter TimeLimit sets a time limit on the time spent in search. The parameter BranchLimit limits the total number of branches (decisions) that are performed by the optimizer.

When a limit is set on the search process of an optimization problem, the call to the optimizer object member function solve terminates when the limit is reached. The function returns true when a solution is available and false otherwise. Note that the number of branches and the time limit can go slightly beyond the specified limit because the best solution found gets "replayed" (regenerated), and this can produce some extra time or branches.

In general, to obtain information on the reason the search ended, you can query the engine using the getInfo member function of the optimizer object (IloCP::getInfo in the C++ API, IloCP.getInfo in the Java™ API and CP.GetInfo in the C# API). with the argument SearchStatus (IloCP::SearchStatus in the C++ API, IloCP.IntInfo.SearchStatus in the Java API, and CP.IntInfo.SearchStatusin the C# API) or SearchStopCause (IloCP::SearchStopCause in the C++ API, IloCP.IntInfo.SearchStopCause in the Java API, and CP.IntInfo.SearchStopCause in the C# API). The meanings of the return values of this function are listed in the CP Optimizer reference manuals.

Another important search parameterization is the one that defines optimality. A solution is considered optimal if there does not exist a solution with a better objective function with respect to an optimality tolerance. This tolerance can be absolute and is controlled with the search parameter OptimalityTolerance. The relative optimality tolerance is controlled with the search parameter RelativeOptimalityTolerance.

For instance, if you consider that an improvement of 10 on your objective function is negligible, you can set this tolerance using the C++ API with the call:

      cp.setParameter(IloCP::OptimalityTolerance, 10);

With this tolerance set, if an optimal solution of a minimization problem is found with an objective value of 900, then there does not exists a solution with an objective value of 890. There may exist solutions with objective values of 891 and higher, but these have been missed due to the tolerance. The default value for this tolerance is 1e-9.

Another example: if you want to find a solution within 3% of the optimal, you set the relative optimality tolerance using the C++ API with the call:

      cp.setParameter(IloCP::RelativeOptimalityTolerance, 0.03);

With this tolerance set, if an optimal solution of a minimization problem is found with an objective value of 900, then there does not exists a solution with an objective value of 873 (= 900 - 900 *0.03). There may exist solutions with objective values of 874 and higher. The default value for this tolerance is 0.0001.

It is important to note that when both a relative and an absolute optimality tolerance are set, they act similarly to constraints, that is only the strongest applies.