Skip to main content

Starting point in CP Optimizer

There are cases where better solutions can be produced more quickly by providing a starting point, an instance of IloSolution, to the optimizer. Here are some typical use cases:

  1. While the optimizer is solving a problem, the session has to be interrupted and the current best solution sol is stored. Later on, a new session for solving the problem is started and the stored solution sol is specified as the starting point of the new search so as to avoid restarting the search from scratch.
  2. For a particular problem, a heuristic is available to produce an initial solution sol. It would be helpful for this feasible solution to be injected in the engine to accelerate the search. One of the techniques for producing such an initial solution can be to augment the original CP Optimizer model with additional constraints (integer variable assignments, presence, precedence or sequencing constraints) to help generate a solution. A typical example in detailed scheduling is mapping producers to consumers thanks to precedence constraints on a reservoir resource.
  3. A multi-objective optimization problem may involve a lexically ordered set of objective functions (f1,f2,...,fn). It could be, for example, a detailed scheduling problem for which the main objective (f1) is to minimize resource allocation costs whereas a secondary objective (f2) is to minimize the makespan of the schedule given an optimal or good resource allocation. In this case, the problem can be solved in n successive steps: first, minimize objective f1 to produce a solution sol1, then, add a constraint to avoid deteriorating f1 and solve the problem with objective function f2 using sol1 as a starting point to produce a solution sol2, etc. Here, the solution to a given step is a feasible solution for the next step.
  4. Given an optimization problem for which finding a first solution is difficult, a possible first step is to relax the problem to make it easier to solve and minimize the constraint violations. For instance, in a detailed scheduling problem, a relaxation can be made by replacing activity deadlines by due dates and minimizing tardiness cost or by setting all activities as optional and minimizing the number of unscheduled activities. If this first step is able to produce a solution with no violations, this feasible solution can be re-injected as starting point to the original optimization problem.
  5. Some applications require solving successive models that are very similar. For instance, in dynamic scheduling, a new request has to be integrated in an existing schedule that was computed in a previous step (notion of work-in-progress). In on-line scheduling, it is necessary to react to various uncertainties of the environment and reschedule when a perturbation occurs (resource breakdown, late activity); here, the new model is similar to the previous one except for the perturbations. In these applications, the previous solution could be used as a starting point to guide the search of the new solve process. Note that here, the previous solution is generally not a feasible solution for the new problem.
  6. Some problems are too complex or too large to be solved in a single model and a hierarchical approach is necessary. A simplification of the original problem involving some relaxation or approximation of some constraints can be solved in a first step in order to fix or to restrict the possible values of some key decision variables of the original problem. Working on a simplified problem allows providing a good solution to the key aspects of the problem without focusing on other, less important details. In a second step, the decisions from this first step can be used as guidelines for solving the original problem by providing the first step decisions as starting point solution.

As seen in the final cases, the starting point provided to the engine does not have to specify a value for each decision variable (it can specify a range of values or no information at all) and does not have to be a feasible solution for the problem being solved. If the starting point provides a fixed value for each decision variable of the problem and if it is feasible, the CP Optimizer search will first visit this solution when traversing the search space. In all other cases, the information contained in the starting point is used as a guideline for the search but there is no guarantee that the solutions traversed by the search will be "close" to the starting point solution.

Note: the starting point information is used by the restart and multi-point search types only. It is not used by the depth-first search.