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

This thesis gives a comprehensive view of the scope of formulations andrelated solution approaches for the cutting stock problem (CSP) and itsvariants. The focus is on branch-and-price approaches. Specializedalgorithms are developed for knapsack subproblems that arise in thecourse of the algorithm. Thorough numerical tests are used to identify good strategiesfor initialization, stabilization, branching, and producingprimal 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 withadditional technical constraints that arise typically in industrialapplications, and a variant where the number of distinct cuttingpatterns 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 toreformulate the CSP. Moreover, we introduce different ways ofmodeling local exchanges in the solution (primal exchanges imply dualconstraints that stabilize the column generation procedure). Somemodels are shown to be valid integer programming (IP) reformulations while others definerelaxations. The dual bounds defined by their LP solution are comparedtheoretically.Then, we study the variants of the knapsack subproblem that arisein a column generation approach to the CSP. The branching constraintsused in the branch-and-price algorithm can result in class bound andsetup cost or the need for a binary decomposition in the subproblem. We show how standard knapsack solvers (dynamic programming approach and specializedbranch-and-bound algorithm) can be extended to these variants of theknapsack 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 stabilizationstrategies 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 weminimize first the waste and then the number of setups