Stratégies de génération de colonnes en programmation entière pour le problème de découpe et ses variantes

Abstract

This thesis gives a comprehensive view of the scope of formulations andrelated solution approaches for the cutting stock problem (CSP) and its variants. The focus is on branch-and-price approaches. Specialized algorithms are developed for knapsack subproblems that arise in thecourse of the algorithm. Thorough numerical tests are used to identify good strategies for initialization, stabilization, branching, and producing primal solutions. Industrial variants of the problem are shown to be tractable for a branch-and-price approach.The models studied are the following: the standard cutting stock andbin packing problems, a variant in which the production levels lie ina prescribed interval of tolerance, the multiple width cutting stockproblem in which stock pieces are of different size, a variant with additional technical constraints that arise typically in industrial applications, and a variant where the number of distinct cutting patterns used is minimized given a waste threshold. First, we consider various formulation of the Cutting Stock Problem(CSP): different models of the knapsack subproblem can be exploited to reformulate the CSP. Moreover, we introduce different ways ofmodeling local exchanges in the solution (primal exchanges imply dual constraints that stabilize the column generation procedure). Some models are shown to be valid integer programming (IP) reformulations while others define relaxations. The dual bounds defined by their LP solution are compared theoretically.Then, we study the variants of the knapsack subproblem that arise in a column generation approach to the CSP. The branching constraints used in the branch-and-price algorithm can result in class bound and setup cost or the need for a binary decomposition in the subproblem. We show how standard knapsack solvers (dynamic programming approach and specialized branch-and-bound algorithm) can be extended to these variants of the knapsack problem.Next, we discuss some branch-and-price implementation strategies. We compare different modes of initialization of the column generation procedure, we present our numerical study of various stabilization strategies to accelerate convergence of the procedure. We compare in particular the impact of the various ways of introducinglocal exchanges in our primal model and other stabilization techniquessuch as dual solution smoothing techniques or penalization from astability center that prevent the fluctuation of the dual variables. To generate the columns we study different strategies based on the use of heuristic columns or on a multiple generation of columns.We also consider the use of heuristics based on column generation to find a primal bound. These are compared to a classic constructive heuristic. Then, we compare the different branching rules that are used in the branch-and-price procedure. Finally, we present numerical results on two industrial applications thatcorrespond to the variant with technical restrictions for which we minimize first the waste and then the number of setups.