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

Incremental Network Optimization: Theory and Algorithms

Author

Listed:
  • Onur Şeref

    (Department of Business Information Technology, Virginia Polytechnic Institute and State University, Blacksburg, Virginia 24061)

  • Ravindra K. Ahuja

    (Department of Industrial and Systems Engineering, University of Florida, Gainesville, Florida 32611)

  • James B. Orlin

    (Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139)

Abstract

In an incremental optimization problem, we are given a feasible solution x 0 of an optimization problem P , and we want to make an incremental change in x 0 that will result in the greatest improvement in the objective function. In this paper, we study the incremental optimization versions of six well-known network problems. We present a strongly polynomial algorithm for the incremental minimum spanning tree problem. We show that the incremental minimum cost flow problem and the incremental maximum flow problem can be solved in polynomial time using Lagrangian relaxation. We consider two versions of the incremental minimum shortest path problem, where increments are measured via arc inclusions and arc exclusions. We present a strongly polynomial time solution for the arc inclusion version and show that the arc exclusion version is NP-complete. We show that the incremental minimum cut problem is NP-complete and that the incremental minimum assignment problem reduces to the minimum exact matching problem, for which a randomized polynomial time algorithm is known.

Suggested Citation

  • Onur Şeref & Ravindra K. Ahuja & James B. Orlin, 2009. "Incremental Network Optimization: Theory and Algorithms," Operations Research, INFORMS, vol. 57(3), pages 586-594, June.
    • Handle: RePEc:inm:oropre:v:57:y:2009:i:3:p:586-594
    DOI: 10.1287/opre.1080.0607
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1080.0607
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1080.0607?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. Gediminas Adomavicius & Alok Gupta, 2005. "Toward Comprehensive Real-Time Bidder Support in Iterative Combinatorial Auctions," Information Systems Research, INFORMS, vol. 16(2), pages 169-185, June.
    2. Ravindra K. Ahuja & Krishna C. Jha & Jian Liu, 2007. "Solving Real-Life Railroad Blocking Problems," Interfaces, INFORMS, vol. 37(5), pages 404-419, October.
    3. Brian L. Dos Santos & Martin L. Bariff, 1988. "A Study of User Interface Aids for Model-Oriented Decision Support Systems," Management Science, INFORMS, vol. 34(4), pages 461-468, April.
    4. George Li & S. Rajagopalan, 1998. "Process Improvement, Quality, and Learning Effects," Management Science, INFORMS, vol. 44(11-Part-1), pages 1517-1532, November.
    5. John D. C. Little, 1970. "Models and Managers: The Concept of a Decision Calculus," Management Science, INFORMS, vol. 16(8), pages 466-485, April.
    6. Peter J. Regan, 2006. "Professional Decision Modeling: Practitioner as Professor," Interfaces, INFORMS, vol. 36(2), pages 142-149, April.
    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. Hradovich, Mikita & Kasperski, Adam & Zieliński, Paweł, 2019. "Robust recoverable 0–1 optimization problems under polyhedral uncertainty," European Journal of Operational Research, Elsevier, vol. 278(1), pages 136-148.
    2. Ximing Wang & Panos M. Pardalos, 2017. "A modified active set algorithm for transportation discrete network design bi-level problem," Journal of Global Optimization, Springer, vol. 67(1), pages 325-342, January.
    3. Fragkos, Ioannis & Cordeau, Jean-François & Jans, Raf, 2021. "Decomposition methods for large-scale network expansion problems," Transportation Research Part B: Methodological, Elsevier, vol. 144(C), pages 60-80.
    4. Chassein, André & Goerigk, Marc & Kasperski, Adam & Zieliński, Paweł, 2018. "On recoverable and two-stage robust selection problems with budgeted uncertainty," European Journal of Operational Research, Elsevier, vol. 265(2), pages 423-436.
    5. Mikita Hradovich & Adam Kasperski & Paweł Zieliński, 2017. "Recoverable robust spanning tree problem under interval uncertainty representations," Journal of Combinatorial Optimization, Springer, vol. 34(2), pages 554-573, August.
    6. Bendotti, Pascale & Chrétienne, Philippe & Fouilhoux, Pierre & Pass-Lanneau, Adèle, 2021. "Dominance-based linear formulation for the Anchor-Robust Project Scheduling Problem," European Journal of Operational Research, Elsevier, vol. 295(1), pages 22-33.
    7. Ali Koç & David P. Morton, 2015. "Prioritization via Stochastic Optimization," Management Science, INFORMS, vol. 61(3), pages 586-603, March.

    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. McCown, R. L., 2002. "Changing systems for supporting farmers' decisions: problems, paradigms, and prospects," Agricultural Systems, Elsevier, vol. 74(1), pages 179-220, October.
    2. Soumyakanti Chakraborty & Anup K. Sen & Amitava Bagchi, 2015. "Addressing the valuation problem in multi-round combinatorial auctions," Information Systems Frontiers, Springer, vol. 17(5), pages 1145-1160, October.
    3. Michael F. Gorman & John-Paul Clarke & Amir Hossein Gharehgozli & Michael Hewitt & René de Koster & Debjit Roy, 2014. "State of the Practice: A Review of the Application of OR/MS in Freight Transportation," Interfaces, INFORMS, vol. 44(6), pages 535-554, December.
    4. Wiesel, Thorsten & Skiera, Bernd & Villanueva, Julian, 2011. "Customer Lifetime Value and Customer Equity Models Using Company-reported Summary Data," Journal of Interactive Marketing, Elsevier, vol. 25(1), pages 20-22.
    5. Stefan N. Groesser & Niklas Jovy, 2016. "Business model analysis using computational modeling: a strategy tool for exploration and decision-making," Journal of Management Control: Zeitschrift für Planung und Unternehmenssteuerung, Springer, vol. 27(1), pages 61-88, February.
    6. Martin Bichler & Johannes Knörr & Felipe Maldonado, 2023. "Pricing in Nonconvex Markets: How to Price Electricity in the Presence of Demand Response," Information Systems Research, INFORMS, vol. 34(2), pages 652-675, June.
    7. de Brentani, Ulrike, 1995. "New industrial service development: Scenarios for success and failure," Journal of Business Research, Elsevier, vol. 32(2), pages 93-103, February.
    8. McCown, R. L., 2002. "Locating agricultural decision support systems in the troubled past and socio-technical complexity of `models for management'," Agricultural Systems, Elsevier, vol. 74(1), pages 11-25, October.
    9. John H. Roberts & Charles J. Nelson & Pamela D. Morrison, 2005. "A Prelaunch Diffusion Model for Evaluating Market Defense Strategies," Marketing Science, INFORMS, vol. 24(1), pages 150-164, August.
    10. Marusia Ivanova, 2007. "Genesis and Evolution of Market Share Predictive Models," Economic Studies journal, Bulgarian Academy of Sciences - Economic Research Institute, issue 2, pages 117-148.
    11. Martin Bichler & Alok Gupta & Wolfgang Ketter, 2010. "Research Commentary ---Designing Smart Markets," Information Systems Research, INFORMS, vol. 21(4), pages 688-699, December.
    12. John R. Hauser & Guilherme (Gui) Liberali & Glen L. Urban, 2014. "Website Morphing 2.0: Switching Costs, Partial Exposure, Random Exit, and When to Morph," Management Science, INFORMS, vol. 60(6), pages 1594-1616, June.
    13. Andris A. Zoltners & Prabhakant Sinha, 2005. "The 2004 ISMS Practice Prize Winner—Sales Territory Design: Thirty Years of Modeling and Implementation," Marketing Science, INFORMS, vol. 24(3), pages 313-331, September.
    14. Eva Ascarza & Scott A. Neslin & Oded Netzer & Zachery Anderson & Peter S. Fader & Sunil Gupta & Bruce G. S. Hardie & Aurélie Lemmens & Barak Libai & David Neal & Foster Provost & Rom Schrift, 2018. "In Pursuit of Enhanced Customer Retention Management: Review, Key Issues, and Future Directions," Customer Needs and Solutions, Springer;Institute for Sustainable Innovation and Growth (iSIG), vol. 5(1), pages 65-81, March.
    15. Zhiling Guo & Gary J. Koehler & Andrew B. Whinston, 2012. "A Computational Analysis of Bundle Trading Markets Design for Distributed Resource Allocation," Information Systems Research, INFORMS, vol. 23(3-part-1), pages 823-843, September.
    16. Dennis Gensch, 2001. "A Marketing-Decision-Support Model for Evaluating and Selecting Concepts for New Products," Interfaces, INFORMS, vol. 31(3_supplem), pages 166-183, June.
    17. Guo, Shu & Choi, Tsan-Ming & Chung, Sai-Ho, 2022. "Self-design fun: Should 3D printing be employed in mass customization operations?," European Journal of Operational Research, Elsevier, vol. 299(3), pages 883-897.
    18. Davide Proserpio & John R. Hauser & Xiao Liu & Tomomichi Amano & Alex Burnap & Tong Guo & Dokyun (DK) Lee & Randall Lewis & Kanishka Misra & Eric Schwarz & Artem Timoshenko & Lilei Xu & Hema Yoganaras, 2020. "Soul and machine (learning)," Marketing Letters, Springer, vol. 31(4), pages 393-404, December.
    19. Claassen, G.D.H., 2014. "Mixed integer (0–1) fractional programming for decision support in paper production industry," Omega, Elsevier, vol. 43(C), pages 21-29.
    20. Jack R. Meredith, 2001. "Reconsidering the Philosophical Basis of OR/MS," Operations Research, INFORMS, vol. 49(3), pages 325-333, June.

    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:57:y:2009:i:3:p:586-594. 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.