Février 2016

Heure:	12:30 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	A Tabu Search Heuristic for a Staff Scheduling Problem
Description:	Stefania Pan Scheduling problems form a very large class of optimization problems en- countered in several industries and organizations of widely different kinds. The particular problem that we consider is a staff scheduling problem, which con- sists of assigning activities to employees by taking into account workload re- quirements and different other constraints (for instance legal, economic, or- ganizational and social constraints). Staff scheduling problems are NP-hard, heuristics methods are often used to deal with large scale practical problems. We focus on constraints which impose minimum and maximum duration on activities. These constraints make the problem difficult to solve. We propose a Tabu Search (TS) approach to deal with the specific staff scheduling problem taking into account workload requirements and activities duration constraints. Computational results show the effectiveness of the proposed approach compar- ing CPLEX solver.

Heure:	12:30 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Primal Heuristics for Branch-and-Price
Description:	Francois Vanderbeck Math heuristics have become an essential component in mixed integer programming (MIP) solvers. Extending generic MIP heuristics, our study outlines generic procedures to build primal solutions in the context of a Branch-and-Price approach and reports on their performance. Rounding the linear relaxation solution of the Dantzig-Wolfe reformu-lation, which is typically tighter than that of the original compact formulation, sometimes produces better solutions than state-of-the-art specialised heuristics as revealed by our numerical experiments. We focus on the so-called diving methods and their combination with diversification-intensification paradigms such as Limited Discrepancy Search, sub-MIPing, relaxation induced neighbourhood search, local branching, and strong branching. The dynamic generation of variables inherent to a column generation approach requires specific adaptation of heuristic paradigms. Our contribution lies in proposing simple strategies to get around these technical issues. Our numerical results on Generalized Assignment, Cutting Stock, and Vertex Coloring problems sets new benchmarks, highlighting the performance of diving heuristics as generic procedures in a column generation context.