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

Tipo di pubblicazione: Articolo su rivista
Tipologia MIUR: Contributo su Rivista > Articolo in rivista
Titolo: Branch-and-price and beam search algorithms for the Variable Cost and Size Bin Packing Problem with optional items
Autori: Baldi M.M.; Crainic T.G.; Perboli G.; Tadei R.
Autori di ateneo:
Titolo del periodico: ANNALS OF OPERATIONS RESEARCH
Tipo di referee: Esperti anonimi
Editore: Springer
Volume: 222
Intervallo pagine: pp. 125-141
Numero di pagine: 17
ISSN: 1572-9338
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.
Data: 2014
Status: Pubblicato
Lingua della pubblicazione: Inglese
Parole chiave: column generation, branch-and-price, beam search, bin packing
Dipartimenti (originale): DAUIN - Dipartimento di Automatica Informatica
Dipartimenti: DAUIN - Dipartimento di Automatica e Informatica
URL correlate:
    Area disciplinare: Area 01 - Scienze matematiche e informatiche > RICERCA OPERATIVA
    Data di deposito: 21 Ott 2014 20:36
    Data ultima modifica (IRIS): 24 Mag 2017 17:14:53
    Data inserimento (PORTO): 29 Mag 2017 19:50
    Numero Identificativo (DOI): 10.1007/s10479-012-1283-2
    Permalink: http://porto.polito.it/id/eprint/2570943
    Link resolver URL: Link resolver link
    Citazioni:

    Il campo presenta il numero di citazioni presenti sulle banche dati Scopus e Web of Science e permette di accedere ai relativi record. Visualizza inoltre il link al record presente su Google Scholar.

    Possono verificarsi discrepanze rispetto ai dati presenti sulle banche dati per i seguenti motivi:

    • Differenze tra i dati riportati su IRIS e quelli presenti nelle banche dati.
    • Il numero di citazioni riportate su PORTO viene estratto mensilmente. Il dato citazionale presente sulle singole banche dati è aggiornato in tempo reale
    • Il numero di citazioni per WoS viene calcolato sulla base delle collezioni in abbonamento (Science citation index Expanded e Conference Proceedings Citation Index)

    Per informazioni o segnalazioni contattare scrivia/porto

    +
    -

    Allegati

    [img] PDF (2014_annals_Branch_and_price_and_beam_search_algorithms.pdf) - Postprint
    Accesso al documento: Non visibile (accessibile solo al proprietario del dato)
    Licenza: Non pubblico - Accesso privato / Ristretto.

    Download (580Kb (594392 bytes)) | Spedisci una richiesta all'autore per una copia del documento
    [img]
    Preview
    PDF (GBPPBrPr.pdf) - Preprint
    Accesso al documento: Visibile (Ad accesso aperto)
    Licenza: Pubblico - Tutti i diritti riservati.

    Download (421Kb (431849 bytes)) | Preview

    Azioni (richiesto il login)

    Visualizza il documento (riservato amministratori) Visualizza il documento (riservato amministratori)

    Statistiche sul Download degli allegati

    Altre statistiche su questa pubblicazione...