Overlapping decomposition in column generation

International audienceTo solve large scale integer programs, decomposition techniques such as column generation or Lagrangian relaxation deeply rely on the chosen structure induced by the dualized constraints. The overlapping decomposition (also referred to as Lagrangian Decomposition or Variable Splitting) is to simultaneously consider several substructures within the same decomposition method. Managing several substructures can be done by duplicating variable subsets which will then be generated through two distinct pricing methods, and linking the corresponding variables using equalities in the master problem.In this work, an overlapping decomposition is proposed to provide strong linear relaxation values for two distinct problems within the framework of Dantzig-Wolfe decomposition: the Reliable Facility Location Problem and the Unit Commitment Problem (UCP).To obtain an evaluation before the column generation convergence, we extend the classical lower bound computation to the overlapping decomposition context. For the UCP, we propose additional reinforcement inequalities.Experimental results show the importance of designing the constraints linking the duplicated variables as inequalities rather than equalities: such inequalities are an important leverage to speed up convergence. The repartition of the dual cost between the two pricing subproblems also improves the convergence. We propose a way to simultaneously use these two concepts of linking inequalities and cost repartition