DI-UMONS : Dépôt institutionnel de l’université de Mons

Recherche transversale
(titres de publication, de périodique et noms de colloque inclus)
2018-07-06 - Colloque/Présentation - communication orale - Anglais - page(s)

Vandaele Arnaud , "One-dimensional cutting stock instances for which few patterns are needed" in 23rd International Symposium on Mathematical Programming, Bordeaux, France, 2018

  • Codes CREF : Mathématiques (DI1100)
  • Unités de recherche UMONS : Mathématique et Recherche opérationnelle (F151)
  • Instituts UMONS : Institut de Recherche en Technologies de l’Information et Sciences de l’Informatique (InforTech)

Abstract(s) :

(Anglais) The Cutting Stock Problem (CSP) is one of the most famous combinatorial optimization problem. An instance of the 1-dimensional CSP consists of d items with different number of copies to cut from large master rolls. The goal is then to produce the required demands with the minimum possible number of master rolls. Each possible combination of items on a master roll is called a pattern. In general, there is an upper bound, exponential in d, for the number of different patterns needed in an optimal solution of a 1-d CSP instance. In this work, we study specific instances for which at most d patterns are needed at the optimum. For example, we study the special case where it is assumed that any k items fit into a pattern but no k+1 do. This particular case is easy to solve, but we show in this talk that there is an optimal solution using at most d different patterns.