08/08/2014

Interactive reoptimization for shift scheduling

The latest results of the "Interactive Metaheuristics" project have been presented at GECCO'14. The corresponding article, entitled "A heuristic approach to schedule reoptimization in the context of interactive optimization" [Meignan 2014], shows the potential benefits of an interactive reoptimization approach.

Shift scheduling

In the paper we propose a reoptimization approach for a shift scheduling problem. Shift scheduling is the task of assigning employees to shifts (e.g. Early shift 7:00-15:00, late shift 15:00-22:00) for a given planning period [Burke et al. 2004, Ernst et al. 2004]. The result, illustrated in Figure 1, is the definition of employees' schedules. Some of the constraints that are generally considered for shift scheduling made the problem complex (See [Lau 1996] and [Brucker et al. 2011] for complexity results). In our study we considered the model of the shift scheduling problem that has been proposed for the International Nurse Rostering Competition held in 2010 (INRC 2010) [Haspeslagh et al. 2012].


Figure 1. A shift scheduling problem with a candidate solution.

Reoptimization in the context of a decision support system

In practice, a model of an optimization problem such as the INRC model 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.


Figure 2. 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 2, 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. For the modification of a planning, instead of manually changing the assignments, the manager indicates some preferences as illustrated in Figure 3. The solution is then reoptimized to introduce the preferences.


Figure 3. 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 article 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 may be defined, it may not be necessary to use in practice a global optimization procedure.
In the paper, we provide some results supporting the fact that 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 4 illustrates this comparison with an actual result.


Figure 4. 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 4 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 the paper, including the performance of ILS against state of the art methods, and results on the impact of the distance constraint.

References

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

[Brucker et al. 2011] P. Brucker, R. Qu, and E. Burke. Personnel scheduling: Models and complexity. European Journal of Operational Research, 210(3):467-473, 2011. DOI: 10.1016/j.ejor.2010.11.017

[Burke et al. 2004] E. K. Burke, P. D. Causmaecker, G. V. Berghe, and H. V. Landeghem. The state of the art of nurse rostering. Journal of Scheduling, 7:441–499, 2004.

[Ernst et al. 2004] A. T. Ernst, H. Jiang, M. Krishnamoorthy, and D. Sier. Staff scheduling and rostering: A review of applications, methods and models. European Journal of Operational Research, 153(1):3–27, 2004.

[Haspeslagh et al. 2012] S. Haspeslagh, P. D. Causmaecker, A. Schaerf, and M. Stølevik. The first international nurse rostering competition 2010. Annals of Operations Research, Online. DOI: 10.1007/s10479-012-1062-0, 2012.

[Lau 1996] H. C. Lau. On the complexity of manpower shift scheduling. Computers and Operations Research, 23(1):93-102, 1996. DOI: 10.1016/0305-0548(94)00094-O

[Meignan 2014] D. Meignan, D. 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


05/06/2013

Project on "Interactive Metaheuristics" funded by the DFG



The DFG (Deutsche Forschungsgemeinschaft) has approved the funding of my research project on interactive optimization. The project will be conducted at the Institute of Computer Science of the University of Osnabrück for a period of two years. This project involves several collaborators in different countries: Dr. David Meignan (Principal investigator, University of Osnabrück, Germany), Pr. Sigrid Knust, Pr. Joachim Hertzberg, and Dipl.-Systemwiss. Florian Bruns (University of Osnabrück, Germany), Dr. Jean-Marc Frayret, and Pr. Gilles Pesant (Polytechnique Montréal, Canada), Pr. Abderrafiâa Koukam, and Pr. Vincent Hilaire (University of Technology of Belfort-Montbéliard, France).

The project funded by the DFG is the continuation of an initial study conducted since April 2012 by Dr. David Meignan and Pr. Sigrid Knust. This work on interactive optimization has been awarded by a grant from Google within the “Google Focused Grant Program on Mathematical Optimization and Combinatorial Optimization” in 2012.

Interactive optimization is the combination of combinatorial optimization methods with expertize of a human operator or user. Over the years, Operation Research has produced numbers of successful computational approaches and software tools for solving hard combinatorial optimization problems of practical significance. However, in several application domains there is still a large gap between research and application of advanced optimization methods, in particular for decision support tools. Interactive optimization is an active and promising paradigm to fill this gap between research and application.

The objectives of this project entitled “Interactive metaheuristics for optimization-based decision support systems” is to develop efficient and practical models, algorithms and software tools for the design of interactive optimisation methods for decision support systems. Two optimization problems have been identified for evaluating the proposed approach. The first one is a staff scheduling problem, whose objective is to determine satisfactory schedules for employees according to workload, legal constraints and staff preferences. The second optimization problem concerns the planning of operation in intermodal transportation.

More information on the project website.
The project description is also available in the GEPRIS database in English as well as in German.

22/04/2013

“Social networks for researchers” in question


Some “Social networks” for researchers use terms and conditions that are in contradiction with the will of sharing and organizing knowledge in a “libre and open-access way”. Although these platforms are potential means of communication in research communities, researchers must be aware of terms of use of these websites. In addition, researchers and institutions must ensure that their research-publication policies are in accordance with these platforms.


Few years ago, a new type of social network appears on the web, “Social networks for researchers/scientists”. For Instance, ResearchGate, Academia and BiomedExperts are originally designed as social portals. Other websites such as Mendeley have progressively introduced social services in their platforms. Utility of these websites have been questioned in diverse blog-posts, Forbes, Blogs.Nature, Presans, MyScienceWork to cite a few.

Personally, I don’t consider that the means of communication provided by these platforms are very useful. I spent very little time on these “social networks”, and prefer to explore collaborative tools for smaller networks (colleagues, collaborators, university, and communities on my research topics).

Beside the potential utility of such platforms, I would like to address in this post potential issues related to terms and conditions of these websites. In my opinion, terms of use of these websites are in contradiction with the will of sharing and organizing knowledge in a “libre and open-access way”, which is not a surprising fact. More important, is the potential conflict between terms of use of these websites and data-handling/publication/copyright policies of research institutions, when such a policy exists.

I illustrate this point with two examples of websites that were recommended to me by colleagues. Note that I do not criticize these platforms for researchers (they present some interesting innovations), but I point out some important aspects for appropriately using them.

First, the content you post on these websites is subject to a licence agreement. For instance, on Academia.edu, the content you post on the website (including abstract, papers or data) is subject to the following licence agreement (in Terms of use):
“By making available any Member Content on or through the Site or Services, you hereby grant to Academia.edu a worldwide, irrevocable, perpetual, non-exclusive, transferable, royalty-free license, with the right to sublicense, to use, view, copy, adapt, modify, distribute, license, sell, transfer, publicly display, publicly perform, transmit, stream, broadcast and otherwise exploit such Member Content only on, through or by means of the Site or Services. Academia.edu does not claim any ownership rights in any Member Content and nothing in these Terms will be deemed to restrict any rights that you may have to use and exploit any Member Content.” (source: Academia.edu, Terms of Use)
These aspects of content rights have to be carefully considered for publishing some research results on websites.

Second, the majority of these platforms restricts or blocks the access of content to non-registered user. These restrictions apply on your list of publications, abstracts, posts or full-texts. For instance, below is a notification for the access of full-texts on ResearchGate.



Clearly, the majority of these “social networks” for researchers are not Libre or open-access platforms, they just monetize research material. Again, researchers have to consider these aspects when they provide content and spend time on these websites. More important, researchers and research institutions must ensure that their data-handling/publication/copyright policies are in accordance with these websites. It is high time for researchers to consider content rights for their research results, and for Universities and funding institutions to provide clear guidelines on research communications and data-handling.

18/01/2013

GECCO 2013, is it worth it to submit?


Submission deadline for the next GECCO conference is approaching (January 31st). Is it worth it to submit a paper to GECCO 2013? Of course, my answer is yes (if you have a paper and the budget). But, it is an opportunity to explain what makes for me a good conference, from a participant point of view. I identified different reasons or criteria to participate to a conference.

Meeting the community: It is one of the main reasons to attend a conference. Listening to presentations and conversing with other researchers is part of a researcher’s work. In addition to learn on your research topic you can also learn about research practices, establish contacts for collaborations, and exchange views on research policies. The fact that some sessions and organizers/session chairs/keynote speakers are focused on your research topic is an important criterion.

Publishing an article: Of course, having an accepted paper to a conference is a way to disseminate your research. Publication and referencing of the proceedings, as well as the opportunity to extend the paper for journals’ special issues, are important aspects. For instance, GECCO will include the proceedings in the ACM Digital Library. Checking the referencing of previous conference editions is a good indicator.

Obtaining feedback on research: This is not as easy as it seems, however the reviews of your paper, the questions and the possible discussions about your presentation are generally valuable. A good review process, an adequate time for the presentation and good conditions for meeting and discussing with other researchers are essential.

Taking one’s mind off things: Yes! And personally I am more productive after this kind of event.

On this topic I found some interesting tips (more particularly for PhD students) by Michael Ernst, "Attending an academic conference". He compiled a list of interesting advice "Advice for researchers and students".

28/10/2012

Publishing and open access

Publication policy is an inevitable topic for researchers and no recent solution has a real consensus. In my opinion, current offers in terms of open publishing are far from being appropriate, at least in computer science. It is very important to keep in mind that the major issue of this question is the variety of interests and actors (and not just a matter of financial interest). Here are some recent points of view that I find interesting in the current debate.

First, the point of view of Professor Moshe Y. Vardi, editor-in-chief of Communications of the ACM. He explains in an article the principle of "Fair Access" pursued by ACM. An interesting point is that "in the case of publishing by a professional association, such as ACM, the authors, as ACM members, are essentially also the publishers." [1]

Another aspect of the debate, evaluation, is addressed in this article about "Open Evaluation" published in "Frontier in Computational Neuroscience" [2]. Again, in this article the close links between the different actors of the scientific publication (here readers and authors) are highlighted.

Finally, a small introduction about open publishing, from "Piled Higher and Deeper" by Jorge Cham, www.phdcomics.com: "What is Open Access". In my opinion, in this video the given view of open-access is over-simplified; however the last slides give interesting elements (“current scientific cultural practices”, “necessity to experiment some publishing practices”, “role of young researchers in the movement for change”)


[1] Moshe Y. Vardi, "Fair Access", Communications of the ACM, May 2012, Vol. 55 No. 5, Page 5
doi:10.1145/2160718.2160719

[2] Nikolaus Kriegeskorte, Alexander Walther, and Diana Deca, "An emerging consensus for open evaluation: 18 visions for the future of scientific publishing", Front. Comput. Neurosci. 6:94. doi:10.3389/fncom.2012.00094