Jeudi 16 février 2017 (14h00, Salle G001)

Abdelkader SBIHI, Ecole de Management de Normandie.

Titre : The sharing problem with conflict graphs: incorporating valid inequalities for an efficient resolution.

Résumé :  In this talk, we study a new version of the sharing problem arising from the real-life which includes conflict constraints between pairs of items, namely SPCI. SPCI is particularly important when conflicting decisions appear for some optimization problems. We say that two items $i$ and $j$ are incompatible for SPCI, if for some graph $G = (V;E)$, the edge $(i; j) \in E \subset V \times V$ is such that $x_i + x_j \leq 1$. We introduce the concept of conflict graphs in combinatorial optimization and some related problems and their results. As an extension to both the sharing and the knapsack problems, we can conclude that the SPCI is NP-hard, but to the best of our knowledge, there exists no established complexity result: (i) for a possible resolution in a polynomial time, (ii) for a PTAS or (iii) for a computed approximation constant . In this talk, we propose several algorithms to approximately solve the SPCI. A fi rst approach is a constructive greedy heuristic aiming at building a feasible starting solution. A second approach is a matheuristic based technique for which we develop a Relax and Reduce (RR) algorithm. We solve a series of relaxed problems which, in turn, lead to a series of reduced problems. Later, to enhance the performance of the RR, we introduce: (i) valid constraints to accelerate the reduced problems resolution and (ii) a chosen metaheuristic to reduce the gap between the upper and lower bounds.