Reoptimization in the context of a decision support system

In practice, a model of an optimization problem such as the shift scheduling problem is likely to contain some inaccuracies. Consequently, a candidate solution provided by an optimization system based on this model may require some adjustments for being realistic. Let’s take the case of a manager that uses an optimization system for determining the planning of the employees of his department. The system provides a candidate solution (planning for all employees); however, the manager knows that it is inappropriate for some employees to work on specific shifts. As a concrete example, arduous tasks that are scheduled on specific time slots may be too hard for young recruits. This constraint is not present in the optimization model and the manager has to adjust the planning to reflect it.

Manual edition of a solution

Figure 1. Manual adjustment of a candidate solution. The change results in multiple unsatisfied constraints that are difficult to solve manually.

If the manager proceeds by manual adjustment, it will be difficult to obtain a good result. As illustrated in Figure 1, a change can deteriorate a solution, and it is difficult to properly adjust the entire solution. The objective of interactive reoptimization is to overcome this difficulty and provide a mechanism for adjusting a solution while minimizing the impact on the cost of the solution. In the proposed reoptimization approach, the adjustment of a solution is an iterative process in which the user specifies preferences on a current candidate solution, and then a procedure re-optimizes the solution to integrate the preferences. The process is iterated until a satisfactory solution is obtained. In our previous example for the modification of a planning, instead of manually changing the assignments, the manager indicates some preferences as illustrated in Figure 2. The solution is then reoptimized to introduce the preferences.

05b_reoptimization

Figure 2. Definition of an assignment preference with the resulting solution obtained by reoptimization. Changes in the reoptimized solution are indicated in yellow.

Optimization versus reoptimization

A reoptimization procedure differs from an optimization procedure on several aspects. First, in comparison to the optimization step, the reoptimization starts with a candidate solution. This initial solution may facilitate the search for a reoptimized solution assuming that only few preferences have been defined by the user of the system. In addition, the reoptimization must take into account the preferences of the user in addition to the initial objectives and constraints of the optimization problem. Next, the computation time for re-optimizing is generally shorter than for the optimization step. Considering the interaction context, reoptimization should last a few seconds to allow the user exploring different alternatives. Finally, the changes which result from the reoptimization should be minimized in order to maintain the consistency of user preferences. If possible, the reoptimized solution should be similar to the initial solution because the preferences of the decision maker have been expressed on the basis of the initial solution. With a completely different reoptimized solution the preferences expressed on the initial solution may lose their meaning. Minimizing the changes in the reoptimized solution should also favors the convergence toward a satisfactory solution for the user.

The reoptimization procedure proposed in the project and presented in [Meignan 2014] has been designed and implemented to meet these specific requirements:

  • An Iterated Local-Search (ILS) procedure is used for both optimization and reoptimization steps. For the reoptimization, the ILS starts with the initial candidate solution.
  • In order to obtain good performance in a few seconds, the ILS procedure exploits high-level parallelism (multi-thread strategy) and delta-evaluation of solutions for local-search.
  • The problem model used for the reoptimization integrates a soft constraint in order to satisfy the preferences defined by the user.
  • Another soft constraint has been integrated to minimize the distance between the initial solution and the reoptimized solution.

Is reoptimization really difficult?

An important question of the study is to evaluate the practical significance of the reoptimization problem. In terms of complexity, the reoptimization problem has the same complexity as the optimization problem [Ausiello at al. 2007]. However, since the reoptimization may start with a good initial solution and only few preferences are generally defined, it may not be necessary to use in practice a global optimization procedure.

In [Meignan 2014] we provide some results supporting the fact that global reoptimization is of practical significance. We considered reoptimization problems in which 5 or 10 assignment preferences are defined over 280 potential shift slots. The reoptimization procedure with ILS has been compared to “pure” local-search procedures. We observed significant gaps in the number of preference satisfied and solution cost reached between the pure local-search procedures and the ILS procedure. Figure 3 illustrates this comparison with an actual result.

reoptim_versus_local

Figure 3. Comparison between ILS and a local-search procedure. The solution obtained with ILS satisfies more preferences than the local-search procedure and reaches a better cost.

The first solution in Figure 3 is the initial solution to be reoptimized. 5 assignment preferences are defined and represented as red crosses. The second solution is obtained with ILS in 2 seconds of computation. 4 preferences have been satisfied, and a cost of 28 has been reached. The third solution is obtained with a hill-climbing procedure based on the 1-swap neighborhood. The number of satisfied preferences is 3, and the cost is 30. The solution obtained with ILS satisfies more preferences than the local-search procedure and reaches a better cost. This result might look trivial, but it clearly shows that the reoptimization cannot be easily handled manually or with a simple recovery procedure. Even for a small number of user preferences, the reoptimization necessitates a global optimization approach.

Additional results are detailed in [Meignan 2014], including the performance of ILS against state of the art methods, and results on the impact of the distance constraint.

References

[Meignan 2014] D. Meignan, A Heuristic Approach to Schedule Reoptimization in the Context of Interactive Optimization. In Genetic and Evolutionary Computation Conference, 461-468, 2014. DOI: 10.1145/2576768.2598213

[Ausiello et al. 2007] G. Ausiello, V. Bonifaci, and B. Escoffier. Computability in Context: Computation and Logic in the Real World, chapter Complexity and Approximation in Reoptimization, pp. 101–129. Imperial College Press, 2007.