David Meignan received his PhD in Computer Science from the University of Belfort-Montbéliard (Belfort, France) in 2008. From 2009 to 2011 he held a postdoctoral position at École Polytechnique de Montréal (Montréal, Canada). From 2011 he works as researcher at the University of Osnabrück (Osnabrück, Germany) where he obtained in April 2012 a research grant from Google for a project on interactive optimization. In June 2013 he received a research grant from the Deutsche Forschungsgemeinschaft (DFG) for a project on interactive metaheuristics. From November 2015, he works as independent developer and IT consultant with a focus on mathematical optimization, data analytics and machine learning.
Research Projects News
The latest results of the “Interactive Metaheuristics” project will be presented at the next Metaheuristics International Conference (MIC’15). The accepted paper “An Experimental Investigation of Reoptimization for Shift Scheduling” (Author: David Meignan) presents the results of an experiment on interactive reoptimization. Read more…
The next Evostar conference will take place at Copenhagen, Denmark, from April 8 to April 10 2015. The submission deadline is November 15, 2014. More information on the website of the conference: www.evostar.org
David Meignan, “An Experimental Investigation of Reoptimization for Shift Scheduling”, MIC’15 (Accepted as full paper), 2015.
Abstract: This paper presents an experimental study conducted with subjects on an interactive reoptimization method applied to a shift scheduling problem. The studied task is the adjustment, by a user, of candidate solutions provided by an optimization system in order to introduce a missing constraint. Two procedures are compared on this task. The first one is a manual adjustment of solutions assisted by a software that dynamically computes the cost of the current solution. The second procedure is based on reoptimization. For this procedure, the user defines some desired changes on a solution, and then a reoptimization method is applied to integrate the changes and reoptimize the rest of the solution. This process is iterated with additional desired changes until a satisfactory solution is obtained. For this interactive approach, the proposed reoptimization procedure is an iterated local search metaheuristic. The experiment, conducted with 16 subjects, provides a quantitative evaluation of the manual and reoptimization approaches. The results show that, even for small local adjustments, the manual modification of a solution has an important impact on the quality of the solution. In addition, the experiment demonstrates the efficiency of the interactive reoptimization approach and the adequacy of the iterated local search method for reoptimizing solutions. Finally, the experiment revealed some limitations of interactive reoptimization that are discussed in this article.
David Meignan, Silvia Schwarze and Stefan Voß, “Improving Local-Search Metaheuristics Through Look-Ahead Policies”, Annals of Mathematics and Artificial Intelligence (online first), 2015.
Abstract: As a basic principle, look-ahead approaches investigate the outcomes of potential future steps to evaluate the quality of alternative search directions. Different policies exist to set up look-ahead methods differing in the object of inspection and in the extensiveness of the search. In this work, two original look-ahead strategies are developed and tested through numerical experiments. The first method introduces a look-ahead mechanism that acts as a hyper-heuristic for comparing and selecting local-search operators. The second method uses a look-ahead strategy on a lower level in order to guide a local-search metaheuristic. The proposed approaches are implemented using a hyper-heuristic framework. They are tested against alternative methods using two different competition benchmarks, including a comparison with results given in literature. Furthermore, in a second set of experiments, a detailed investigation regarding the influence of particular parameter values is executed for one method. The experiments reveal that the inclusion of a simple look-ahead principle into an iterated local-search procedure significantly improves the outcome regarding the considered benchmarks.