4 Presentations

• 
  03:30 PM - 03:55 PM

  The meet-in-the-middle principle for cutting and packing problems

  • Jean-François Côté, presenter, Université Laval
  • Manuel Iori, Università degli Studi di Modena e Reggio Emilia

  Cutting and packing (C&P) is a fundamental research area that models a large number of managerial and industrial optimization issues. A solution to a C&P problem basically consists in a set of one- or multi- dimensional items packed in/cut from one or more bins, by satisfying problem constraints and minimizing a given objective function. Normal patterns are a well-known C&P technique used to build solutions where each item is aligned to the bottom of the bin along each dimension. The rationale in their use is that they can reduce the search space while preserving optimality, but the drawback is that their number grows consistently when the number of items and the size of the bin increase. In this paper we propose a new set of patterns, called meet-in-the-middle, that lead to several interesting results. Their computation is achieved with the same time complexity as that of the normal patterns, but their number is never higher, and in practical applications it frequently shows reductions of about 50%. The new patterns are applied to improve some state-of-the-art C&P techniques, including arc-flow formulations, combinatorial branch-and- bound algorithms, and mixed integer linear programs. The efficacy of the improved techniques is assessed by extensive computational tests on a number of relevant applications.

• 
  03:55 PM - 04:20 PM

  The two-dimensional bin packing problem with guillotine cuts and stacked boards

  • Johan Oppen, presenter, Molde University College

  We present a new variant of the two-dimensional bin packing problem with guillotine cuts, where a stack of boards, all with the same cutting pattern, are cut simultaneously to save time. Computational testing shows that significant amounts of time can be saved without increasing the amount of waste.

• 
  04:20 PM - 04:45 PM

  Dual feasible functions and their application in cutting and packing

  • José Manuel Valério de Carvalho, presenter, Universidade do Minho
  • Cláudio Alves, Universidade do Minho
  • François Clautiaux, Université de Bordeaux
  • Jürgen Rietz, Universidade do Minho

  Dual Feasible Functions (DFF) provide feasible dual solutions of strong models that correspond to lower bounds that are often very close to the lower bounds provided by column generation models. As DFF can be computed quickly, the computational burden can be small when compared to column generation algorithms. We address applications in cutting and packing, and in particular the 2-dimensional vector packing problem, where an optimal layout for a set of items with two independent dimensions has to be found within the boundaries of a rectangle. Many practical applications in areas such as telecommunications, transportation and production planning involve this problem. Several difficulties arise when one wants to generalize the results obtained for 1-dimensional DFF to the m-dimensional case. They are induced by the fact that the comparison between item sizes has to be done component wise, and therefore, monotonicity and super additivity take a different sense. We focus on the computation of fast lower bounds. Our computational results show that these functions can approximate very efficiently the best known lower bounds for this problem and improve significantly the convergence of branch-and-bound algorithms.

• 
  04:45 PM - 05:10 PM

  Pseudo-polynomial formulations and recent improvements for the variable size bin packing problem

  • Maxence Delorme, presenter, Université de Bologne
  • Manuel Iori, Università degli Studi di Modena e Reggio Emilia

  We study the 1-dimensional variable size bin-packing problem. First, we review two main mathematical formulations, “One-Cut” and “Arc-Flow” proposed in the literature and show that, under certain conditions, the two formulations are equivalent. Then, we adapt some of the most powerful techniques proposed recently in the literature for the single size case (graph reduction and node aggregation) to provide a competitive algorithm for solving the problem.