2016

Heure:	12:30 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	An Exact Semidefinite Programming Approach for the Max-Mean Dispersion Problem
Description:	Michele Garraffa This work proposes an exact algorithm for the Max-Mean Dispersion Problem (Max-Mean DP), an NP-hard combinatorial optimization problem whose aim is to select the subset of a set such that the average distance between elements is maximized. The problem admits a natural non-convex quadratic fractional formulation from which a semidefinite programming (SDP) relaxation can be derived. In general, semidefinite relaxations have been successfully used to determine tight (but usually computationally expensive) lower/upper bounds for challenging NP-hard problems, such as the Quadratic Assignment Problem and the Quadratic Knapsack Problem. The semidefinite relaxation for the Max-Mean DP can be further tightened by means of a cutting plane algorithm which iteratively adds the most violated triangular inequalities. The proposed approach embeds the SDP relaxation and the cutting plane algorithm into a branch and bound framework to solve Max-Mean DP instances to optimality. To authors' knowledge, this is the first exact algorithm that has been proposed for this problem. Computational experiments show that the proposed method is able to solve to optimality in reasonable time instances with up 100 elements, while standard methods for fractional combinatorial optimization manage instances whose size is less then or equal to 75. The presented approach can be generalized to other combinatorial problems with a quadratic fractional objective and linear constraints.

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.

Heure:	12:30 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Combinatorial Optimization subject to PDE constraints
Description:	Christoph Buchheim We investigate a class of optimal control problems where the control parameters are binary variables, which are supposed to be static and probably subject to combinatorial constraints. Additionally, the problem contains state constraints involving semi-linear elliptic partial differential equations (PDEs). As an example, the binary variables may correspond to the activation of given heat sources attached to a metal sheet, the optimization problem then consists in switching on the smallest number of heat sources such that the point-wise temperature of the metal sheet is in a specified range. Our main result is that each state is a concave function in the binary control vector. This allows us to define an outer approximation scheme in which we alternate between the solution of a non-linear PDE and an integer linear program. Using this approach, we can solve instances on up to 2000 binary variables to global optimality.