Browsing by Author "Serairi, M."

Now showing 1 - 3 of 3

Metadata only
A computational study of lower bounds for the two dimensional bin packing problem
(Elsevier, 2010-08-01) Serairi, M.; Haouari, Mohamed; Industrial Engineering; HAOUARI, Mohamed
We survey lower bounds for the variant of the two-dimensional bin packing problem where items cannot be rotated. We prove that the dominance relation claimed by Carlier et al. between their lower bounds and those of Boschetti and Mingozzi is not valid. We analyze the performance of lower bounds from the literature and we provide the results of a computational experiment.
Metadata only
Heuristics for the variable sized bin-packing problem
(Elsevier, 2009-10) Haouari, Mohamed; Serairi, M.; Industrial Engineering; HAOUARI, Mohamed
We investigate the one-dimensional variable-sized bin-packing problem. This problem requires packing a set of items into a minimum-cost set of bins of unequal sizes and costs. Six optimization-based heuristics for this problem are presented and compared. We analyze their empirical performance on a large set of randomly generated test instances with up to 2000 items and seven bin types. The first contribution of this paper is to provide evidence that a set covering heuristic proves to be highly effective and capable of delivering very-high quality solutions within short CPU times. In addition, we found that a simple subset-sum problem-based heuristic consistently outperforms heuristics from the literature while requir- ing extremely short CPU times.
Metadata only
Relaxations and exact solution of the variable sized bin packing problem
(Springer Science+Business Media, 2011-03) Haouari, Mohamed; Serairi, M.; Industrial Engineering; HAOUARI, Mohamed
We address a generalization of the classical one-dimensional bin packing problem with unequal bin sizes and costs. We investigate lower bounds for this problem as well as exact algorithms. The main contribution of this paper is to show that embedding a tight network flow-based lower bound, dominance rules, as well as an effective knapsack-based heuristic in a branch-and-bound algorithm yields very good performance. In addition, we show that the particular case with all weight items larger than a third the largest bin capacity can be restated and solved in polynomial-time as a maximum-weight matching problem in a nonbipartite graph. We report the results of extensive computational experiments that provide evidence that large randomly generated instances are optimally solved within moderate CPU times.