IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v46y2012i2p281-295.html
   My bibliography  Save this article

Fixed-Charge Transportation with Product Blending

Author

Listed:
  • Dimitri J. Papageorgiou

    (H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332)

  • Alejandro Toriello

    (Daniel J. Epstein Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, California 90089)

  • George L. Nemhauser

    (H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332)

  • Martin W. P. Savelsbergh

    (School of Mathematical and Physical Sciences, University of Newcastle, Callaghan NSW 2308, Australia)

Abstract

Numerous planning models within the chemical, petroleum, and process industries involve coordinating the movement of raw materials in distribution networks so they can be blended into final products. The uncapacitated fixed-charge transportation problem with blending (FCTPwB) studied in this paper captures a core structure encountered in many of these environments. We model the FCTPwB as a mixed-integer linear program, and we derive two classes of facets, both exponential in size, for the convex hull of solutions for the problem with a single consumer and show that they can be separated in polynomial time. Furthermore, we prove that, in certain situations, these classes of facets along with the continuous relaxation of the original constraints yield a description of the convex hull. Finally, we present a computational study that demonstrates that these classes of facets are effective in reducing the integrality gap and solution time for more general instances of the FCTPwB with arc capacities and multiple consumers.

Suggested Citation

  • Dimitri J. Papageorgiou & Alejandro Toriello & George L. Nemhauser & Martin W. P. Savelsbergh, 2012. "Fixed-Charge Transportation with Product Blending," Transportation Science, INFORMS, vol. 46(2), pages 281-295, May.
    • Handle: RePEc:inm:ortrsc:v:46:y:2012:i:2:p:281-295
    DOI: 10.1287/trsc.1110.0381
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.1110.0381
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.1110.0381?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. Sun, Minghe & Aronson, Jay E. & McKeown, Patrick G. & Drinka, Dennis, 1998. "A tabu search heuristic procedure for the fixed charge transportation problem," European Journal of Operational Research, Elsevier, vol. 106(2-3), pages 441-456, April.
    2. Zonghao Gu & George L. Nemhauser & Martin W.P. Savelsbergh, 2000. "Sequence Independent Lifting in Mixed Integer Programming," Journal of Combinatorial Optimization, Springer, vol. 4(1), pages 109-129, March.
    3. Zonghao Gu & George L. Nemhauser & Martin W. P. Savelsbergh, 1999. "Lifted Cover Inequalities for 0-1 Integer Programs: Complexity," INFORMS Journal on Computing, INFORMS, vol. 11(1), pages 117-123, February.
    4. Gavin J. Bell & Bruce W. Lamar & Chris A. Wallace, 1999. "Capacity improvement, penalties, and the fixed charge transportation problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 46(4), pages 341-355, June.
    5. VAN ROY, Tony J. & WOLSEY, Laurence A., 1985. "Valid inequalities and separation for uncapacitated fixed charge networks," LIDAM Reprints CORE 671, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    6. Calvin W. DeWitt & Leon S. Lasdon & Allan D. Waren & Donald A. Brenner & Simon A. Melhem, 1989. "OMEGA: An Improved Gasoline Blending System for Texaco," Interfaces, INFORMS, vol. 19(1), pages 85-101, February.
    7. Frode Rømo & Asgeir Tomasgard & Lars Hellemo & Marte Fodstad & Bjørgulf Haukelidsæter Eidesen & Birger Pedersen, 2009. "Optimizing the Norwegian Natural Gas Production and Transport," Interfaces, INFORMS, vol. 39(1), pages 46-56, February.
    8. Udatta S. Palekar & Mark H. Karwan & Stanley Zionts, 1990. "A Branch-and-Bound Method for the Fixed Charge Transportation Problem," Management Science, INFORMS, vol. 36(9), pages 1092-1105, September.
    9. Billy Rigby & Leon S. Lasdon & Allan D. Waren, 1995. "The Evolution of Texaco’s Blending Systems: From OMEGA to StarBlend," Interfaces, INFORMS, vol. 25(5), pages 64-83, October.
    10. M. W. Padberg & T. J. Van Roy & L. A. Wolsey, 1985. "Valid Linear Inequalities for Fixed Charge Problems," Operations Research, INFORMS, vol. 33(4), pages 842-861, August.
    11. Bruce W. Lamar & Chris A. Wallace, 1997. "Revised-Modified Penalties for Fixed Charge Transportation Problems," Management Science, INFORMS, vol. 43(10), pages 1431-1436, October.
    12. Jesús Sáez Aguado, 2009. "Fixed Charge Transportation Problems: a new heuristic approach based on Lagrangean relaxation and the solving of core problems," Annals of Operations Research, Springer, vol. 172(1), pages 45-69, November.
    13. Padberg, M.W. & Van Roy, T.J. & Wolsey, L.A., 1985. "Valid linear inequalities for fixed charge problems," LIDAM Reprints CORE 656, 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. Bertazzi, Luca & Maggioni, Francesca, 2018. "A stochastic multi-stage fixed charge transportation problem: Worst-case analysis of the rolling horizon approach," European Journal of Operational Research, Elsevier, vol. 267(2), pages 555-569.
    2. Baskoro, Firly Rachmaditya & Takahashi, Katsuhiko & Morikawa, Katsumi & Nagasawa, Keisuke, 2022. "Multi-objective optimization on total cost and carbon dioxide emission of coal supply for coal-fired power plants in Indonesia," Socio-Economic Planning Sciences, Elsevier, vol. 81(C).
    3. Yifu Chen & Christos T. Maravelias, 2020. "Preprocessing algorithm and tightening constraints for multiperiod blend scheduling: cost minimization," Journal of Global Optimization, Springer, vol. 77(3), pages 603-625, July.
    4. Arigoni, Ashley & Newman, Alexandra & Turner, Cameron & Kaptur, Casey, 2017. "Optimizing global thermal coal shipments," Omega, Elsevier, vol. 72(C), pages 118-127.
    5. Korai, Muhammad Safar & Mahar, Rasool Bux & Uqaili, Muhammad Aslam, 2017. "The feasibility of municipal solid waste for energy generation and its existing management practices in Pakistan," Renewable and Sustainable Energy Reviews, Elsevier, vol. 72(C), pages 338-353.

    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. Yogesh Agarwal & Yash Aneja, 2012. "Fixed-Charge Transportation Problem: Facets of the Projection Polyhedron," Operations Research, INFORMS, vol. 60(3), pages 638-654, June.
    2. Erika Buson & Roberto Roberti & Paolo Toth, 2014. "A Reduced-Cost Iterated Local Search Heuristic for the Fixed-Charge Transportation Problem," Operations Research, INFORMS, vol. 62(5), pages 1095-1106, October.
    3. Jesús Sáez Aguado, 2009. "Fixed Charge Transportation Problems: a new heuristic approach based on Lagrangean relaxation and the solving of core problems," Annals of Operations Research, Springer, vol. 172(1), pages 45-69, November.
    4. Jeffery L. Kennington & Charles D. Nicholson, 2010. "The Uncapacitated Time-Space Fixed-Charge Network Flow Problem: An Empirical Investigation of Procedures for Arc Capacity Assignment," INFORMS Journal on Computing, INFORMS, vol. 22(2), pages 326-337, May.
    5. Binyuan Chen & Simge Küçükyavuz & Suvrajeet Sen, 2011. "Finite Disjunctive Programming Characterizations for General Mixed-Integer Linear Programs," Operations Research, INFORMS, vol. 59(1), pages 202-210, February.
    6. Wei-Kun Chen & Liang Chen & Mu-Ming Yang & Yu-Hong Dai, 2018. "Generalized coefficient strengthening cuts for mixed integer programming," Journal of Global Optimization, Springer, vol. 70(1), pages 289-306, January.
    7. Fred Glover & Hanif Sherali, 2005. "Some Classes of Valid Inequalities and Convex Hull Characterizations for Dynamic Fixed-Charge Problems under Nested Constraints," Annals of Operations Research, Springer, vol. 140(1), pages 215-233, November.
    8. Quentin Louveaux & Laurence Wolsey, 2007. "Lifting, superadditivity, mixed integer rounding and single node flow sets revisited," Annals of Operations Research, Springer, vol. 153(1), pages 47-77, September.
    9. Alper Atamtürk & Martin Savelsbergh, 2005. "Integer-Programming Software Systems," Annals of Operations Research, Springer, vol. 140(1), pages 67-124, November.
    10. Diego Klabjan & George L. Nemhauser, 2002. "A Polyhedral Study of Integer Variable Upper Bounds," Mathematics of Operations Research, INFORMS, vol. 27(4), pages 711-739, November.
    11. Jawahar, N. & Balaji, A.N., 2009. "A genetic algorithm for the two-stage supply chain distribution problem associated with a fixed charge," European Journal of Operational Research, Elsevier, vol. 194(2), pages 496-537, April.
    12. Roberto Roberti & Enrico Bartolini & Aristide Mingozzi, 2015. "The Fixed Charge Transportation Problem: An Exact Algorithm Based on a New Integer Programming Formulation," Management Science, INFORMS, vol. 61(6), pages 1275-1291, June.
    13. Mohammed Alfaki & Dag Haugland, 2014. "A cost minimization heuristic for the pooling problem," Annals of Operations Research, Springer, vol. 222(1), pages 73-87, November.
    14. ORTEGA, Francisco & WOLSEY, Laurence, 2000. "A branch-and-cut algorithm for the single commodity uncapacitated fixed charge network flow problem," LIDAM Discussion Papers CORE 2000049, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    15. Masoud Yaghini & Mohammad Karimi & Mohadeseh Rahbar & Mohammad Hassan Sharifitabar, 2015. "A Cutting-Plane Neighborhood Structure for Fixed-Charge Capacitated Multicommodity Network Design Problem," INFORMS Journal on Computing, INFORMS, vol. 27(1), pages 48-58, February.
    16. Richard Laundy & Michael Perregaard & Gabriel Tavares & Horia Tipi & Alkis Vazacopoulos, 2009. "Solving Hard Mixed-Integer Programming Problems with Xpress-MP: A MIPLIB 2003 Case Study," INFORMS Journal on Computing, INFORMS, vol. 21(2), pages 304-313, May.
    17. Adlakha, Veena & Kowalski, Krzysztof & Wang, Simi & Lev, Benjamin & Shen, Wenjing, 2014. "On approximation of the fixed charge transportation problem," Omega, Elsevier, vol. 43(C), pages 64-70.
    18. Retsef Levi & Andrea Lodi & Maxim Sviridenko, 2008. "Approximation Algorithms for the Capacitated Multi-Item Lot-Sizing Problem via Flow-Cover Inequalities," Mathematics of Operations Research, INFORMS, vol. 33(2), pages 461-474, May.
    19. Kowalski, Krzysztof & Lev, Benjamin & Shen, Wenjing & Tu, Yan, 2014. "A fast and simple branching algorithm for solving small scale fixed-charge transportation problem," Operations Research Perspectives, Elsevier, vol. 1(1), pages 1-5.
    20. Andrew P. Armacost & Cynthia Barnhart & Keith A. Ware, 2002. "Composite Variable Formulations for Express Shipment Service Network Design," Transportation Science, INFORMS, vol. 36(1), pages 1-20, February.

    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:ortrsc:v:46:y:2012:i:2:p:281-295. 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.