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.

A branch-and-price algorithm for the variable size bin packing problem with minimum filling constraint / A. Bettinelli, A. Ceselli, G. Righini. - In: ANNALS OF OPERATIONS RESEARCH. - ISSN 0254-5330. - 179:1(2010 Sep), pp. 221-241. [10.1007/s10479-008-0452-9]

A branch-and-price algorithm for the variable size bin packing problem with minimum filling constraint

A. Bettinelli
Primo
;
A. Ceselli
Secondo
;
G. Righini
Ultimo
2010-09

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.
Bin packing ; Column generation ; Branch-and-price.
Settore MAT/09 - Ricerca Operativa
Settore INF/01 - Informatica
Article (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/145918
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 11
social impact