The Experts below are selected from a list of 6834 Experts worldwide ranked by ideXlab platform

Jordi Pereira - One of the best experts on this subject based on the ideXlab platform.

  • procedures for the Bin Packing Problem with precedence constraints
    European Journal of Operational Research, 2016
    Co-Authors: Jordi Pereira
    Abstract:

    Abstract The Bin Packing Problem with precedence constraints (BPP-P) is a recently proposed variation of the classical Bin Packing Problem (BPP), which corresponds to a basic model featuring many underlying characteristics of several scheduling and assembly line balancing Problems. The formulation builds upon the BPP by incorporating precedence constraints among items, which force successor items to be packed into later Bins than their predecessors. In this paper we propose a dynamic programming based heuristic, and a modified exact enumeration procedure to solve the Problem. These methods make use of several new lower bounds and dominance rules tailored for the Problem in hand. The results of a computational experiment show the effectiveness of the proposed methods, which are able to close all of the previous open instances from the benchmark instance set within very reduced running times.

  • Procedures for the Bin Packing Problem with precedence constraints
    European Journal of Operational Research, 2016
    Co-Authors: Jordi Pereira
    Abstract:

    The Bin Packing Problem with precedence constraints (BPP-P) is a recently proposed variation of the classical Bin Packing Problem (BPP), which corresponds to a basic model featuring many underlying characteristics of several scheduling and assembly line balancing Problems. The formulation builds upon the BPP by incorporating precedence constraints among items, which force successor items to be packed into later Bins than their predecessors.

Giovanni Righini - One of the best experts on this subject based on the ideXlab platform.

  • a branch and price algorithm for the variable size Bin Packing Problem with minimum filling constraint
    Annals of Operations Research, 2010
    Co-Authors: Andrea Bettinelli, Alberto Ceselli, Giovanni Righini
    Abstract:

    In this paper we consider a variation of the Bin Packing Problem in which Bins of different types have different costs and capacities. Furthermore, each Bin has to be filled at least to a certain level, which depends on its type. We present a set partitioning formulation and an exact optimization algorithm which exploits column generation and specialized heuristics. We compare our algorithm with the general purpose solver ILOG CPLEX, running on two compact ILP formulations and we report on experimental results on instances we have generated from data-sets for the variable size Bin Packing Problem.

  • An Optimization Algorithm for the Ordered Open-End Bin-Packing Problem
    Operations Research, 2008
    Co-Authors: Alberto Ceselli, Giovanni Righini
    Abstract:

    The ordered open-end Bin-Packing Problem is a variant of the Bin-Packing Problem in which the items to be packed are sorted in a given order and the capacity of each Bin can be exceeded by the last item packed into the Bin. We present a branch-and-price algorithm for its exact optimization. The pricing subProblem is a special variant of the Binary knapsack Problem, in which the items are ordered and the last one does not consume capacity. We present a specialized optimization algorithm for this subProblem. The speed of the column generation algorithm is improved by subgradient optimization steps, allowing for multiple pricing and variable fixing. Computational results are presented on instances of different sizes and items with different correlations between their size and their position in the given order.

Bora Uçar - One of the best experts on this subject based on the ideXlab platform.

  • Comments on the hierarchically structured Bin Packing Problem
    Information Processing Letters, 2015
    Co-Authors: Thomas Lambert, Loris Marchal, Bora Uçar
    Abstract:

    We study the hierarchically structured Bin Packing Problem. In this Problem, the items to be packed into Bins are at the leaves of a tree. The objective of the Packing is to minimize the total number of Bins into which the descendants of an internal node are packed, summed over all internal nodes. We investigate an existing algorithm and make a correction to the analysis of its approximation ratio. Further results regarding the structure of an optimal solution and a strengthened inapproximability result are given.

  • Comments on the hierarchically structured Bin Packing Problem
    Information Processing Letters, 2015
    Co-Authors: Thomas Lambert, Loris Marchal, Bora Uçar
    Abstract:

    We study the hierarchically structured Bin Packing Problem. In this Problem, the items to be packed into Bins are at the leaves of a tree. The objective of the Packing is to minimize the total number of Bins into which the descendants of an internal node are packed, summed over all internal nodes. We investigate an existing algorithm and make a correction to the analysis of its approximation ratio. Further results regarding the structure of an optimal solution and a strengthened inapproximability result are given. No APTAS for hierarchically structured Bin Packing Problem with non-uniform weights.A condition for a known heuristic to have 3/2 approximation guarantee.Best post-order is not always best.

Joseph Y.-t. Leung - One of the best experts on this subject based on the ideXlab platform.

  • The Ordered Open-End Bin-Packing Problem
    Operations Research, 2003
    Co-Authors: Jian Yang, Joseph Y.-t. Leung
    Abstract:

    We study a variant of the classical Bin-Packing Problem, the ordered open-end Bin-Packing Problem, where first a Bin can be filled to a level above 1 as long as the removal of the last piece brings the Bin's level back to below 1 and second, the last piece is the largest-indexed piece among all pieces in the Bin. We conduct both worst-case and average-case analyses for the Problem. In the worst-case analysis, pieces of size 1 play distinct roles and render the analysis more difficult with their presence. We give lower bounds for the performance ratio of any online algorithm for cases both with and without the 1-pieces, and in the case without the 1-pieces, identify an online algorithm whose worst-case performance ratio is less than 2 and an offline algorithm with good worst-case performance. In the average-case analysis, assuming that pieces are independently and uniformly drawn from [0, 1], we find the optimal asymptotic average ratio of the number of occupied Bins over the number of pieces. We also introduce other online algorithms and conduct simulation study on the average-case performances of all the proposed algorithms.

  • a note on an open end Bin Packing Problem
    Journal of Scheduling, 2001
    Co-Authors: Joseph Y.-t. Leung, Moshe Dror, Gilbert H. Young
    Abstract:

    We consider a variant of the classical one-dimensional Bin Packing Problem, which we call the open-end Bin Packing Problem. Suppose that we are given a list L=(p1,p2,…,pn) of n pieces, where pj denotes both the name and the size of the jth piece in L, and an infinite collection of infinite-capacity Bins. A Bin can always accommodate a piece if the Bin has not yet reached a level of C or above, but it will be closed as soon as it reaches that level. Our goal is to find a Packing that uses the minimum number of Bins. In this article, we first show that the open-end Bin Packing Problem remains strongly NP-hard. We then show that any online algorithm must have an asymptotic worst-case ratio of at least 2, and there is a simple online algorithm with exactly this ratio. Finally, we give an offline algorithm that is a fully polynomial approximation scheme with respect to the asymptotic worst-case ratio. Copyright © 2001 John Wiley & Sons, Ltd.

  • A note on an open‐end Bin Packing Problem
    Journal of Scheduling, 2001
    Co-Authors: Joseph Y.-t. Leung, Moshe Dror, Gilbert H. Young
    Abstract:

    We consider a variant of the classical one-dimensional Bin Packing Problem, which we call the open-end Bin Packing Problem. Suppose that we are given a list L=(p1,p2,…,pn) of n pieces, where pj denotes both the name and the size of the jth piece in L, and an infinite collection of infinite-capacity Bins. A Bin can always accommodate a piece if the Bin has not yet reached a level of C or above, but it will be closed as soon as it reaches that level. Our goal is to find a Packing that uses the minimum number of Bins. In this article, we first show that the open-end Bin Packing Problem remains strongly NP-hard. We then show that any online algorithm must have an asymptotic worst-case ratio of at least 2, and there is a simple online algorithm with exactly this ratio. Finally, we give an offline algorithm that is a fully polynomial approximation scheme with respect to the asymptotic worst-case ratio. Copyright © 2001 John Wiley & Sons, Ltd.

Daniele Vigo - One of the best experts on this subject based on the ideXlab platform.

  • heuristic algorithms for the three dimensional Bin Packing Problem
    European Journal of Operational Research, 2002
    Co-Authors: Andrea Lodi, Silvano Martello, Daniele Vigo
    Abstract:

    Abstract The Three-Dimensional Bin Packing Problem (3BP) consists of allocating, without overlapping, a given set of three-dimensional rectangular items to the minimum number of three-dimensional identical finite Bins. The Problem is NP-hard in the strong sense, and finds many industrial applications. We introduce a Tabu Search framework exploiting a new constructive heuristic for the evaluation of the neighborhood. Extensive computational results on standard benchmark instances show the effectiveness of the approach with respect to exact and heuristic algorithms from the literature.

  • the three dimensional Bin Packing Problem
    Operations Research, 2000
    Co-Authors: Silvano Martello, David Pisinger, Daniele Vigo
    Abstract:

    The Problem addressed in this paper is that of orthogonally Packing a given set of rectangular-shaped items into the minimum number of three-dimensional rectangular Bins. The Problem is strongly NP-hard and extremely difficult to solve in practice. Lower bounds are discussed, and it is proved that the asymptotic worst-case performance ratio of the continuous lower bound is ?. An exact algorithm for filling a single Bin is developed, leading to the definition of an exact branch-and-bound algorithm for the three-dimensional Bin Packing Problem, which also incorporates original approximation algorithms. Extensive computational results, involving instances with up to 90 items, are presented: It is shown that many instances can be solved to optimality within a reasonable time limit.