In the Variable Cost and Size Bin Packing Problem with optional items, a set of items characterized by volume and profit and a set of bins of different types characterized by volume and cost are given. The goal consists in selecting those items and bins which optimize an objective function which combines the cost of the used bins and the profit of the selected items.We propose two methods to tackle the problem: branch-and-price as an exact method and beam search as a heuristics, derived from the branch-and-price. Our branchand- price method is characterized by a two level branching strategy. At the first level the branching is performed on the number of available bins for each bin type. At the second level it consists on pairs of items which can or cannot be loaded together. Exploiting the branchand- price skeleton, we then present a variegated beam search heuristics, characterized by different beam sizes. We finally present extensive computational results which show a high accuracy of the exact method and a very good efficiency of the proposed heuristics.

Branch-and-price and beam search algorithms for the Variable Cost and Size Bin Packing Problem with optional items / Baldi, MAURO MARIA; Crainic, T. G.; Perboli, Guido; Tadei, Roberto. - In: ANNALS OF OPERATIONS RESEARCH. - ISSN 1572-9338. - STAMPA. - 222:(2014), pp. 125-141. [10.1007/s10479-012-1283-2]

Branch-and-price and beam search algorithms for the Variable Cost and Size Bin Packing Problem with optional items

BALDI, MAURO MARIA;PERBOLI, Guido;TADEI, Roberto
2014

Abstract

In the Variable Cost and Size Bin Packing Problem with optional items, a set of items characterized by volume and profit and a set of bins of different types characterized by volume and cost are given. The goal consists in selecting those items and bins which optimize an objective function which combines the cost of the used bins and the profit of the selected items.We propose two methods to tackle the problem: branch-and-price as an exact method and beam search as a heuristics, derived from the branch-and-price. Our branchand- price method is characterized by a two level branching strategy. At the first level the branching is performed on the number of available bins for each bin type. At the second level it consists on pairs of items which can or cannot be loaded together. Exploiting the branchand- price skeleton, we then present a variegated beam search heuristics, characterized by different beam sizes. We finally present extensive computational results which show a high accuracy of the exact method and a very good efficiency of the proposed heuristics.
File in questo prodotto:
File Dimensione Formato  
2014-annals-Branch-and-price and beam search algorithms.pdf

non disponibili

Tipologia: 2. Post-print / Author's Accepted Manuscript
Licenza: Non Pubblico - Accesso privato/ristretto
Dimensione 580.46 kB
Formato Adobe PDF
580.46 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
GBPPBrPr.pdf

accesso aperto

Tipologia: 1. Preprint / submitted version [pre- review]
Licenza: PUBBLICO - Tutti i diritti riservati
Dimensione 421.73 kB
Formato Adobe PDF
421.73 kB Adobe PDF Visualizza/Apri
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: https://hdl.handle.net/11583/2570943
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo