IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v290y2021i3p857-869.html
   My bibliography  Save this article

A specialized interior-point algorithm for huge minimum convex cost flows in bipartite networks

Author

Listed:
  • Castro, Jordi
  • Nasini, Stefano

Abstract

The computation of the Newton direction is the most time consuming step of interior-point methods. This direction was efficiently computed by a combination of Cholesky factorizations and conjugate gradients in a specialized interior-point method for block-angular structured problems. In this work we refine this algorithmic approach to solve very large instances of minimum cost flows problems in bipartite networks, for convex objective functions with diagonal Hessians (i.e., either linear, quadratic or separable nonlinear objectives). For this class of problems the specialized algorithm only required the solution of a system by conjugate gradients at each interior-point iteration, avoiding Cholesky factorizations. After analyzing the theoretical properties of the interior-point method for this kind of problems, we provide extensive computational experiments with linear and quadratic instances of up to one billion arcs (corresponding to 200 nodes and five million nodes in each subset of the node partition, respectively). For linear and quadratic instances our approach is compared with the barriers algorithms of CPLEX (both standard path-following and homogeneous-self-dual); for linear instances it is also compared with the different algorithms of the state-of-the-art network flow solver LEMON (namely: network simplex, capacity scaling, cost scaling and cycle canceling). The specialized interior-point approach significantly outperformed the other approaches in most of the linear and quadratic transportation instances tested. In particular, it always provided a solution within the time limit; and (like LEMON, and unlike CPLEX) it never exhausted the memory of the server used for the runs. For assignment problems the network algorithms in LEMON were the most efficient option.

Suggested Citation

  • Castro, Jordi & Nasini, Stefano, 2021. "A specialized interior-point algorithm for huge minimum convex cost flows in bipartite networks," European Journal of Operational Research, Elsevier, vol. 290(3), pages 857-869.
  • Handle: RePEc:eee:ejores:v:290:y:2021:i:3:p:857-869
    DOI: 10.1016/j.ejor.2020.10.027
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221720309036
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2020.10.027?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. Morton Klein, 1967. "A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems," Management Science, INFORMS, vol. 14(3), pages 205-220, November.
    2. López-Ramos, Francisco & Nasini, Stefano & Sayed, Mohamed H., 2020. "An integrated planning model in centralized power systems," European Journal of Operational Research, Elsevier, vol. 287(1), pages 361-377.
    3. M. Jenabi & S. Fatemi Ghomi & S. Torabi & S. Hosseinian, 2015. "Acceleration strategies of Benders decomposition for the security constraints power system expansion planning," Annals of Operations Research, Springer, vol. 235(1), pages 337-369, December.
    4. Andrew V. Goldberg & Robert E. Tarjan, 1990. "Finding Minimum-Cost Circulations by Successive Approximation," Mathematics of Operations Research, INFORMS, vol. 15(3), pages 430-466, August.
    5. Jordi Castro & Stefano Nasini, 2017. "On Geometrical Properties of Preconditioners in IPMs for Classes of Block-Angular Problems," Post-Print hal-01745326, HAL.
    6. Willard I. Zangwill, 1968. "Minimum Concave Cost Flows in Certain Networks," Management Science, INFORMS, vol. 14(7), pages 429-450, March.
    7. Jordi Castro & Stefano Nasini & Francisco Saldanha-Da-Gama, 2017. "A cutting-plane approach for large-scale capacitated multi-period facility location using a specialized interior-point method," Post-Print hal-01745324, HAL.
    8. Yankai Cao & Carl D. Laird & Victor M. Zavala, 2016. "Clustering-based preconditioning for stochastic programs," Computational Optimization and Applications, Springer, vol. 64(2), pages 379-406, June.
    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. Filippo Zanetti & Jacek Gondzio, 2023. "An Interior Point–Inspired Algorithm for Linear Programs Arising in Discrete Optimal Transport," INFORMS Journal on Computing, INFORMS, vol. 35(5), pages 1061-1078, September.
    2. Nasini, Stefano & Nessah, Rabia, 2021. "An almost exact solution to the min completion time variance in a single machine," European Journal of Operational Research, Elsevier, vol. 294(2), pages 427-441.
    3. Nasini, Stefano & Nessah, Rabia, 2024. "Time-flexible min completion time variance in a single machine by quadratic programming," European Journal of Operational Research, Elsevier, vol. 312(2), pages 427-444.
    4. Nasini, Stefano & Labbé, Martine & Brotcorne, Luce, 2022. "Multi-market portfolio optimization with conditional value at risk," European Journal of Operational Research, Elsevier, vol. 300(1), pages 350-365.

    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. López-Ramos, Francisco & Nasini, Stefano & Sayed, Mohamed H., 2020. "An integrated planning model in centralized power systems," European Journal of Operational Research, Elsevier, vol. 287(1), pages 361-377.
    2. Wang, Yan & Wang, Junwei, 2019. "Integrated reconfiguration of both supply and demand for evacuation planning," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 130(C), pages 82-94.
    3. Nasini, Stefano & Nessah, Rabia, 2021. "An almost exact solution to the min completion time variance in a single machine," European Journal of Operational Research, Elsevier, vol. 294(2), pages 427-441.
    4. Sauvey, Christophe & Melo, Teresa & Correia, Isabel, 2019. "Two-phase heuristics for a multi-period capacitated facility location problem with service-differentiated customers," Technical Reports on Logistics of the Saarland Business School 16, Saarland University of Applied Sciences (htw saar), Saarland Business School.
    5. Cortés, Pablo & Muñuzuri, Jesús & Guadix, José & Onieva, Luis, 2013. "Optimal algorithm for the demand routing problem in multicommodity flow distribution networks with diversification constraints and concave costs," International Journal of Production Economics, Elsevier, vol. 146(1), pages 313-324.
    6. Hark‐Chin Hwang & Wilco van den Heuvel, 2012. "Improved algorithms for a lot‐sizing problem with inventory bounds and backlogging," Naval Research Logistics (NRL), John Wiley & Sons, vol. 59(3‐4), pages 244-253, April.
    7. Durga Prasad Khanal & Urmila Pyakurel & Tanka Nath Dhamala & Stephan Dempe, 2022. "Efficient Algorithms for Abstract Flow with Partial Switching," SN Operations Research Forum, Springer, vol. 3(4), pages 1-17, December.
    8. Karla E. Bourland & Candace Arai Yano, 1996. "Lot sizing when yields increase during the production run," Naval Research Logistics (NRL), John Wiley & Sons, vol. 43(8), pages 1035-1047, December.
    9. Martel, Alain & Gascon, Andre, 1998. "Dynamic lot-sizing with price changes and price-dependent holding costs," European Journal of Operational Research, Elsevier, vol. 111(1), pages 114-128, November.
    10. Xiao, Yiyong & Kaku, Ikou & Zhao, Qiuhong & Zhang, Renqian, 2011. "A reduced variable neighborhood search algorithm for uncapacitated multilevel lot-sizing problems," European Journal of Operational Research, Elsevier, vol. 214(2), pages 223-231, October.
    11. Vernon Ning Hsu, 2000. "Dynamic Economic Lot Size Model with Perishable Inventory," Management Science, INFORMS, vol. 46(8), pages 1159-1169, August.
    12. Piñeyro, Pedro & Viera, Omar, 2010. "The economic lot-sizing problem with remanufacturing and one-way substitution," International Journal of Production Economics, Elsevier, vol. 124(2), pages 482-488, April.
    13. Zhao Zhang & Zaixin Lu & Xianyue Li & Xiaohui Huang & Ding-Zhu Du, 2019. "Online hole healing for sensor coverage," Journal of Global Optimization, Springer, vol. 75(4), pages 1111-1131, December.
    14. Trudeau, Christian, 2009. "Network flow problems and permutationally concave games," Mathematical Social Sciences, Elsevier, vol. 58(1), pages 121-131, July.
    15. Chung‐Lun Li & Jinwen Ou & Vernon N. Hsu, 2012. "Dynamic lot sizing with all‐units discount and resales," Naval Research Logistics (NRL), John Wiley & Sons, vol. 59(3‐4), pages 230-243, April.
    16. Hark-Chin Hwang & Hyun-Soo Ahn & Philip Kaminsky, 2013. "Basis Paths and a Polynomial Algorithm for the Multistage Production-Capacitated Lot-Sizing Problem," Operations Research, INFORMS, vol. 61(2), pages 469-482, April.
    17. Daniel Baena & Jordi Castro & Antonio Frangioni, 2020. "Stabilized Benders Methods for Large-Scale Combinatorial Optimization, with Application to Data Privacy," Management Science, INFORMS, vol. 66(7), pages 3051-3068, July.
    18. Steven J. Erlebacher & Medini R. Singh, 1999. "Optimal Variance Structures and Performance Improvement of Synchronous Assembly Lines," Operations Research, INFORMS, vol. 47(4), pages 601-618, August.
    19. 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.
    20. Rahmaniani, Ragheb & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2017. "The Benders decomposition algorithm: A literature review," European Journal of Operational Research, Elsevier, vol. 259(3), pages 801-817.

    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:eee:ejores:v:290:y:2021:i:3:p:857-869. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.