IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v203y2013i1p217-23410.1007-s10479-011-0857-8.html
   My bibliography  Save this article

Cascading Knapsack Inequalities: reformulation of a crude oil distribution problem

Author

Listed:
  • Roger Rocha
  • Ignacio Grossmann
  • Marcus Poggi de Aragão

Abstract

In this paper we consider the problem in which crude oil is shipped from platforms to terminals using oil tankers at minimum transportation cost. This subproblem, which arises in petroleum supply chain models, can be surprisingly expensive to solve with a straightforward formulation involving inventory balances. We present a reformulation that has a special structure defined in this paper as Cascading Knapsack Inequalities. This is used as the basis for deriving tight reformulations for special cases with a limited number of classes of tankers. Numerical results are presented to demonstrate that significant computational savings can be accomplished with the proposed reformulations. Copyright Springer Science+Business Media, LLC 2013

Suggested Citation

  • Roger Rocha & Ignacio Grossmann & Marcus Poggi de Aragão, 2013. "Cascading Knapsack Inequalities: reformulation of a crude oil distribution problem," Annals of Operations Research, Springer, vol. 203(1), pages 217-234, March.
    • Handle: RePEc:spr:annopr:v:203:y:2013:i:1:p:217-234:10.1007/s10479-011-0857-8
    DOI: 10.1007/s10479-011-0857-8
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-011-0857-8
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-011-0857-8?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Robert Bixby & Edward Rothberg, 2007. "Progress in computational mixed integer programming—A look back from the other side of the tipping point," Annals of Operations Research, Springer, vol. 149(1), pages 37-41, February.
    2. Robert Ashford, 2007. "Mixed integer programming: A historical perspective with Xpress-MP," Annals of Operations Research, Springer, vol. 149(1), pages 5-17, February.
    3. Andrew J. Miller & Laurence A. Wolsey, 2003. "Tight Mip Formulation for Multi-Item Discrete Lot-Sizing Problems," Operations Research, INFORMS, vol. 51(4), pages 557-565, August.
    4. Alper Atamtürk & Martin Savelsbergh, 2005. "Integer-Programming Software Systems," Annals of Operations Research, Springer, vol. 140(1), pages 67-124, November.
    5. Brahimi, Nadjib & Dauzere-Peres, Stephane & Najid, Najib M. & Nordli, Atle, 2006. "Single item lot sizing problems," European Journal of Operational Research, Elsevier, vol. 168(1), pages 1-16, January.
    6. MILLER, Andrew J. & WOLSEY, Laurence A., 2003. "Tight MIP formulations for multi-item discrete lot-sizing problems," LIDAM Reprints CORE 1639, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    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. Agostinho Agra & Marielle Christiansen & Kristine S. Ivarsøy & Ida Elise Solhaug & Asgeir Tomasgard, 2017. "Combined ship routing and inventory management in the salmon farming industry," Annals of Operations Research, Springer, vol. 253(2), pages 799-823, June.
    2. Dimitri J. Papageorgiou & Ahmet B. Keha & George L. Nemhauser & Joel Sokol, 2014. "Two-Stage Decomposition Algorithms for Single Product Maritime Inventory Routing," INFORMS Journal on Computing, INFORMS, vol. 26(4), pages 825-847, November.
    3. Hemmati, Ahmad & Hvattum, Lars Magnus & Christiansen, Marielle & Laporte, Gilbert, 2016. "An iterative two-phase hybrid matheuristic for a multi-product short sea inventory-routing problem," European Journal of Operational Research, Elsevier, vol. 252(3), pages 775-788.
    4. Papageorgiou, Dimitri J. & Nemhauser, George L. & Sokol, Joel & Cheon, Myun-Seok & Keha, Ahmet B., 2014. "MIRPLib – A library of maritime inventory routing problem instances: Survey, core model, and benchmark results," European Journal of Operational Research, Elsevier, vol. 235(2), pages 350-366.
    5. Gustavo Souto dos Santos Diz & Silvio Hamacher & Fabricio Oliveira, 2019. "A robust optimization model for the maritime inventory routing problem," Flexible Services and Manufacturing Journal, Springer, vol. 31(3), pages 675-701, September.

    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. Francesco Gaglioppa & Lisa A. Miller & Saif Benjaafar, 2008. "Multitask and Multistage Production Planning and Scheduling for Process Industries," Operations Research, INFORMS, vol. 56(4), pages 1010-1025, August.
    2. Karina Copil & Martin Wörbelauer & Herbert Meyr & Horst Tempelmeier, 2017. "Simultaneous lotsizing and scheduling problems: a classification and review of models," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(1), pages 1-64, January.
    3. Patrick Gemander & Wei-Kun Chen & Dieter Weninger & Leona Gottwald & Ambros Gleixner & Alexander Martin, 2020. "Two-row and two-column mixed-integer presolve using hashing-based pairing methods," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 8(3), pages 205-240, October.
    4. Yaman, Hande & Sen, Alper, 2008. "Manufacturer's mixed pallet design problem," European Journal of Operational Research, Elsevier, vol. 186(2), pages 826-840, April.
    5. Mathieu Van Vyve, 2007. "Algorithms for Single-Item Lot-Sizing Problems with Constant Batch Size," Mathematics of Operations Research, INFORMS, vol. 32(3), pages 594-613, August.
    6. Lee, Younsoo & Lee, Kyungsik, 2020. "Lot-sizing and scheduling in flat-panel display manufacturing process," Omega, Elsevier, vol. 93(C).
    7. Tobias Achterberg & Robert E. Bixby & Zonghao Gu & Edward Rothberg & Dieter Weninger, 2020. "Presolve Reductions in Mixed Integer Programming," INFORMS Journal on Computing, INFORMS, vol. 32(2), pages 473-506, April.
    8. Toy, Ayhan Özgür & Berk, Emre, 2013. "Dynamic lot sizing for a warm/cold process: Heuristics and insights," International Journal of Production Economics, Elsevier, vol. 145(1), pages 53-66.
    9. Melega, Gislaine Mara & de Araujo, Silvio Alexandre & Jans, Raf, 2018. "Classification and literature review of integrated lot-sizing and cutting stock problems," European Journal of Operational Research, Elsevier, vol. 271(1), pages 1-19.
    10. David R. Morrison & Jason J. Sauppe & Wenda Zhang & Sheldon H. Jacobson & Edward C. Sewell, 2017. "Cyclic best first search: Using contours to guide branch‐and‐bound algorithms," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(1), pages 64-82, February.
    11. Ricardo M. Lima & Ignacio E. Grossmann, 2017. "On the solution of nonconvex cardinality Boolean quadratic programming problems: a computational study," Computational Optimization and Applications, Springer, vol. 66(1), pages 1-37, January.
    12. Irfan Ertugrul & Aysegul Tus Isik, 2009. "Production Planning for a Winery With Mixed Integer Programming Model," Ege Academic Review, Ege University Faculty of Economics and Administrative Sciences, vol. 9(2), pages 375-387.
    13. Moo-Sung Sohn & Jiwoong Choi & Hoseog Kang & In-Chan Choi, 2017. "Multiobjective Production Planning at LG Display," Interfaces, INFORMS, vol. 47(4), pages 279-291, August.
    14. Hark‐Chin Hwang, 2007. "Dynamic lot‐sizing model with production time windows," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(6), pages 692-701, September.
    15. Helber, Stefan & Sahling, Florian, 2010. "A fix-and-optimize approach for the multi-level capacitated lot sizing problem," International Journal of Production Economics, Elsevier, vol. 123(2), pages 247-256, February.
    16. W. Brian Lambert & Andrea Brickey & Alexandra M. Newman & Kelly Eurek, 2014. "Open-Pit Block-Sequencing Formulations: A Tutorial," Interfaces, INFORMS, vol. 44(2), pages 127-142, April.
    17. Akbalik, Ayse & Penz, Bernard, 2009. "Exact methods for single-item capacitated lot sizing problem with alternative machines and piece-wise linear production costs," International Journal of Production Economics, Elsevier, vol. 119(2), pages 367-379, June.
    18. Pan, Zhendong & Tang, Jiafu & Liu, Ou, 2009. "Capacitated dynamic lot sizing problems in closed-loop supply chain," European Journal of Operational Research, Elsevier, vol. 198(3), pages 810-821, November.
    19. Chung-Lun Li & Qingying Li, 2016. "Polynomial-Time Solvability of Dynamic Lot Size Problems," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 33(03), pages 1-20, June.
    20. Shyam S. G. Perumal & Jesper Larsen & Richard M. Lusby & Morten Riis & Tue R. L. Christensen, 2022. "A column generation approach for the driver scheduling problem with staff cars," Public Transport, Springer, vol. 14(3), pages 705-738, October.

    More about this item

    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:spr:annopr:v:203:y:2013:i:1:p:217-234:10.1007/s10479-011-0857-8. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.