IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v56y2008i2p425-436.html
   My bibliography  Save this article

An Optimization Algorithm for the Ordered Open-End Bin-Packing Problem

Author

Listed:
  • Alberto Ceselli

    (Dipartimento di Tecnologie dell'Informazione, Università degli Studi di Milano, 26013 Crema, Italy)

  • Giovanni Righini

    (Dipartimento di Tecnologie dell'Informazione, Università degli Studi di Milano, 26013 Crema, Italy)

Abstract

The ordered open-end bin-packing problem is a variant of the bin-packing problem in which the items to be packed are sorted in a given order and the capacity of each bin can be exceeded by the last item packed into the bin. We present a branch-and-price algorithm for its exact optimization. The pricing subproblem is a special variant of the binary knapsack problem, in which the items are ordered and the last one does not consume capacity. We present a specialized optimization algorithm for this subproblem. The speed of the column generation algorithm is improved by subgradient optimization steps, allowing for multiple pricing and variable fixing. Computational results are presented on instances of different sizes and items with different correlations between their size and their position in the given order.

Suggested Citation

  • Alberto Ceselli & Giovanni Righini, 2008. "An Optimization Algorithm for the Ordered Open-End Bin-Packing Problem," Operations Research, INFORMS, vol. 56(2), pages 425-436, April.
    • Handle: RePEc:inm:oropre:v:56:y:2008:i:2:p:425-436
    DOI: 10.1287/opre.1070.0415
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1070.0415
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1070.0415?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Lodi, Andrea & Martello, Silvano & Monaci, Michele, 2002. "Two-dimensional packing problems: A survey," European Journal of Operational Research, Elsevier, vol. 141(2), pages 241-252, September.
    2. Jian Yang & Joseph Y.-T. Leung, 2003. "The Ordered Open-End Bin-Packing Problem," Operations Research, INFORMS, vol. 51(5), pages 759-770, October.
    3. Egon Balas & Eitan Zemel, 1980. "An Algorithm for Large Zero-One Knapsack Problems," Operations Research, INFORMS, vol. 28(5), pages 1130-1154, October.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Lixin Tang & Gongshu Wang & Zhi-Long Chen, 2014. "Integrated Charge Batching and Casting Width Selection at Baosteel," Operations Research, INFORMS, vol. 62(4), pages 772-787, August.
    2. Menezes, Gustavo Campos & Mateus, Geraldo Robson & Ravetti, Martín Gómez, 2017. "A branch and price algorithm to solve the integrated production planning and scheduling in bulk ports," European Journal of Operational Research, Elsevier, vol. 258(3), pages 926-937.
    3. Delle Donne, Diego & Alfandari, Laurent & Archetti, Claudia & Ljubić, Ivana, 2023. "Freight-on-Transit for urban last-mile deliveries: A strategic planning approach," Transportation Research Part B: Methodological, Elsevier, vol. 169(C), pages 53-81.
    4. Hu, Qian & Zhu, Wenbin & Qin, Hu & Lim, Andrew, 2017. "A branch-and-price algorithm for the two-dimensional vector packing problem with piecewise linear cost function," European Journal of Operational Research, Elsevier, vol. 260(1), pages 70-80.
    5. Maxence Delorme & Manuel Iori, 2020. "Enhanced Pseudo-polynomial Formulations for Bin Packing and Cutting Stock Problems," INFORMS Journal on Computing, INFORMS, vol. 32(1), pages 101-119, January.
    6. Soto Cardona, Osman Camilo & Mejía Argueta, Christopher & Sarmiento, Alfonso Tullio, 2015. "A cost-efficient method to optimize package size in emerging marketsAuthor-Name: Gámez Albán, Harol Mauricio," European Journal of Operational Research, Elsevier, vol. 241(3), pages 917-926.
    7. Mauro Dell'Amico & José Carlos Díaz Díaz & Manuel Iori, 2012. "The Bin Packing Problem with Precedence Constraints," Operations Research, INFORMS, vol. 60(6), pages 1491-1504, December.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Esmaeil Afrashteh & Behrooz Alizadeh & Fahimeh Baroughi, 2020. "Optimal approaches for upgrading selective obnoxious p-median location problems on tree networks," Annals of Operations Research, Springer, vol. 289(2), pages 153-172, June.
    2. Francisco Trespalacios & Ignacio E. Grossmann, 2017. "Symmetry breaking for generalized disjunctive programming formulation of the strip packing problem," Annals of Operations Research, Springer, vol. 258(2), pages 747-759, November.
    3. Andrzej Kozik, 2017. "Handling precedence constraints in scheduling problems by the sequence pair representation," Journal of Combinatorial Optimization, Springer, vol. 33(2), pages 445-472, February.
    4. M. Drozdowski & N. V. Shakhlevich, 2021. "Scheduling divisible loads with time and cost constraints," Journal of Scheduling, Springer, vol. 24(5), pages 507-521, October.
    5. Anshu Ranjan & Pramod Khargonekar & Sartaj Sahni, 2017. "Offline first-fit decreasing height scheduling of power loads," Journal of Scheduling, Springer, vol. 20(5), pages 527-542, October.
    6. Russo, Mauro & Sforza, Antonio & Sterle, Claudio, 2013. "An improvement of the knapsack function based algorithm of Gilmore and Gomory for the unconstrained two-dimensional guillotine cutting problem," International Journal of Production Economics, Elsevier, vol. 145(2), pages 451-462.
    7. Bayliss, Christopher & Currie, Christine S.M. & Bennell, Julia A. & Martinez-Sykora, Antonio, 2021. "Queue-constrained packing: A vehicle ferry case study," European Journal of Operational Research, Elsevier, vol. 289(2), pages 727-741.
    8. López-Camacho, Eunice & Terashima-Marín, Hugo & Ochoa, Gabriela & Conant-Pablos, Santiago Enrique, 2013. "Understanding the structure of bin packing problems through principal component analysis," International Journal of Production Economics, Elsevier, vol. 145(2), pages 488-499.
    9. W. D. D. Madhavee & N. Saldin & U. C. Vaidyarathna & C. J. Jayawardene, 2018. "A Practical Application of the Generalized Cutting Stock Algorithm," Academic Journal of Applied Mathematical Sciences, Academic Research Publishing Group, vol. 4(3), pages 15-21, 03-2018.
    10. David Pisinger, 1999. "Core Problems in Knapsack Algorithms," Operations Research, INFORMS, vol. 47(4), pages 570-575, August.
    11. M Hifi & M Michrafy, 2006. "A reactive local search-based algorithm for the disjunctively constrained knapsack problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(6), pages 718-726, June.
    12. Renata Mansini & M. Grazia Speranza, 2012. "CORAL: An Exact Algorithm for the Multidimensional Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 24(3), pages 399-415, August.
    13. A Ghanmi & R H A D Shaw, 2008. "Modelling and analysis of Canadian Forces strategic lift and pre-positioning options," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(12), pages 1591-1602, December.
    14. Reinaldo Morabito & Vitória Pureza, 2010. "A heuristic approach based on dynamic programming and and/or-graph search for the constrained two-dimensional guillotine cutting problem," Annals of Operations Research, Springer, vol. 179(1), pages 297-315, September.
    15. Altay, Nezih & Robinson Jr., Powell E. & Bretthauer, Kurt M., 2008. "Exact and heuristic solution approaches for the mixed integer setup knapsack problem," European Journal of Operational Research, Elsevier, vol. 190(3), pages 598-609, November.
    16. Jakob Puchinger & Günther R. Raidl & Ulrich Pferschy, 2010. "The Multidimensional Knapsack Problem: Structure and Algorithms," INFORMS Journal on Computing, INFORMS, vol. 22(2), pages 250-265, May.
    17. Andrea Lodi & Silvano Martello & Michele Monaci & Claudio Cicconetti & Luciano Lenzini & Enzo Mingozzi & Carl Eklund & Jani Moilanen, 2011. "Efficient Two-Dimensional Packing Algorithms for Mobile WiMAX," Management Science, INFORMS, vol. 57(12), pages 2130-2144, December.
    18. Igor Kierkosz & Maciej Luczak, 2014. "A hybrid evolutionary algorithm for the two-dimensional packing problem," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 22(4), pages 729-753, December.
    19. Iori, Manuel & de Lima, Vinícius L. & Martello, Silvano & Miyazawa, Flávio K. & Monaci, Michele, 2021. "Exact solution techniques for two-dimensional cutting and packing," European Journal of Operational Research, Elsevier, vol. 289(2), pages 399-415.
    20. Torsten Buchwald & Kirsten Hoffmann & Guntram Scheithauer, 2014. "Relations between capacity utilization, minimal bin size and bin number," Annals of Operations Research, Springer, vol. 217(1), pages 55-76, June.

    More about this item

    Keywords

    combinatorial optimization;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:56:y:2008:i:2:p:425-436. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.