Constraint Programming Contribution to Benders Decomposition: A Case Study

The aim of this paper is to demonstrate that CP could be a better candidate than MIP for solving the master problem within a Benders decomposition approach. Our demonstration is based on a case study of a workforce scheduling problem encountered in a large call center of Bouygues Telecom, a French mobile phone operator. Our experiments show that CP can advantageously replace MIP for the implementation of the master problem due to its greater ability to efficiently manage a wide variety of constraints such as the ones occurring in time tabling applications.