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:
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.