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. Peter J. Regan, 2006. "Professional Decision Modeling: Practitioner as Professor," Interfaces, INFORMS, vol. 36(2), pages 142-149, April.
    2. 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.
    3. John D. C. Little, 1970. "Models and Managers: The Concept of a Decision Calculus," Management Science, INFORMS, vol. 16(8), pages 466-485, April.
    4. 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.
    5. George Li & S. Rajagopalan, 1998. "Process Improvement, Quality, and Learning Effects," Management Science, INFORMS, vol. 44(11-Part-1), pages 1517-1532, November.
    6. Ravindra K. Ahuja & Krishna C. Jha & Jian Liu, 2007. "Solving Real-Life Railroad Blocking Problems," Interfaces, INFORMS, vol. 37(5), pages 404-419, 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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. Ali Koç & David P. Morton, 2015. "Prioritization via Stochastic Optimization," Management Science, INFORMS, vol. 61(3), pages 586-603, March.
    7. 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.

    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. Paulson Gjerde, Kathy A. & Slotnick, Susan A., 2004. "Quality and reputation: The effects of external and internal factors over time," International Journal of Production Economics, Elsevier, vol. 89(1), pages 1-20, May.
    2. McCown, R. L., 2002. "Changing systems for supporting farmers' decisions: problems, paradigms, and prospects," Agricultural Systems, Elsevier, vol. 74(1), pages 179-220, October.
    3. Zhong, Tao & Young, Rhonda, 2010. "Multiple Choice Knapsack Problem: Example of planning choice in transportation," Evaluation and Program Planning, Elsevier, vol. 33(2), pages 128-137, May.
    4. Jin, Jian Gang & Zhao, Jun & Lee, Der-Horng, 2013. "A column generation based approach for the Train Network Design Optimization problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 50(C), pages 1-17.
    5. Borgonovo, E., 2010. "Sensitivity analysis with finite changes: An application to modified EOQ models," European Journal of Operational Research, Elsevier, vol. 200(1), pages 127-138, January.
    6. 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.
    7. Terrence August & Hyoduk Shin & Tunay I. Tunca, 2018. "Generating Value Through Open Source: Software Service Market Regulation and Licensing Policy," Information Systems Research, INFORMS, vol. 29(1), pages 186-205, March.
    8. 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.
    9. 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.
    10. Fuglseth, A. M. & Grønhaug, K., 1997. "IT-enabled redesign of complex and dynamic business processes: the case of bank credit evaluation," Omega, Elsevier, vol. 25(1), pages 93-106, February.
    11. den Hartigh, E. & Langerak, F. & Commandeur, H.R., 2002. "The Effects of Self-Reinforcing Mechanisms on Firm Performance," ERIM Report Series Research in Management ERS-2002-46-MKT, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    12. David A McDonald, 2016. "The weight of water: Benchmarking for public water services," Environment and Planning A, , vol. 48(11), pages 2181-2200, November.
    13. 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.
    14. 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.
    15. Donald G. Morrison & Jagmohan S. Raju, 2004. "50th Anniversary Article: The Marketing Department in Management Science: Its History, Contributions, and the Future," Management Science, INFORMS, vol. 50(4), pages 425-428, April.
    16. 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.
    17. 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.
    18. Albers, Sönke, 2012. "Optimizable and implementable aggregate response modeling for marketing decision support," International Journal of Research in Marketing, Elsevier, vol. 29(2), pages 111-122.
    19. 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.
    20. 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.

    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.