Relaxations and exact solution of the variable sized bin packing problem

Name: Relaxations and exact solution of the variable sized bin packing problem
Author: Haouari, Mohamed, Serairi, M.

İsim	Relaxations and exact solution of the variable sized bin packing problem
Yazar	Haouari, Mohamed, Serairi, M.
Basım Tarihi:	2011-03
Basım Yeri	- Springer Science+Business Media
Konu	Bin packing problem, Lower bounds, Branch-and-bound
Tür	Süreli Yayın
Dil	İngilizce
Dijital	Evet
Yazma	Hayır
Kütüphane:	Özyeğin Üniversitesi
Demirbaş Numarası	0926-6003
Kayıt Numarası	782f3d01-4f12-4577-9752-9a6ec007d126
Lokasyon	Industrial Engineering
Tarih	2011-03
Notlar	Due to copyright restrictions, the access to the full text of this article is only available via subscription.
Örnek Metin	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.
DOI	10.1007/s10589-009-9276-z
Cilt	48

Kaynağa git Özyeğin Üniversitesi

Aramaya Dön

Özyeğin Üniversitesi

Kaynağa git

Relaxations and exact solution of the variable sized bin packing problem

Yazar Haouari, Mohamed, Serairi, M.

Basım Tarihi 2011-03

Basım Yeri - Springer Science+Business Media

Konu Bin packing problem, Lower bounds, Branch-and-bound

Tür Süreli Yayın

Dil İngilizce

Dijital Evet

Yazma Hayır

Kütüphane Özyeğin Üniversitesi

Demirbaş Numarası 0926-6003

Kayıt Numarası 782f3d01-4f12-4577-9752-9a6ec007d126

Lokasyon Industrial Engineering

Tarih 2011-03

Notlar Due to copyright restrictions, the access to the full text of this article is only available via subscription.

Örnek Metin 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.

DOI 10.1007/s10589-009-9276-z

Cilt 48