IDEAS home Printed from https://ideas.repec.org/a/kap/compec/v25y2005i4p303-326.html
   My bibliography  Save this article

Dantzig—Wolfe Decomposition of Variational Inequalities

Author

Listed:
  • J. Fuller
  • William Chung

Abstract

The creation and ongoing management of a large economic model can be greatly simplified if the model is managed in separate smaller pieces defined, e.g. by region or commodity. For this purpose, we define an extension of Dantzig–Wolfe decomposition for the variational inequality (VI) problem, a modeling framework that is widely used for models of competitive or oligopolistic markets. The subproblem, a collection of independent smaller models, is a relaxed VI missing some “difficult” constraints. The subproblem is modified at each iteration by information passed from the last solution of the master problem in a manner analogous to Dantzig–Wolfe decomposition for optimization models. The master problem is a VI which forms convex combinations of proposals from the subproblem, and enforces the difficult constraints. A valid stopping condition is derived in which a scalar quantity, called the “convergence gap,” is monitored. The convergence gap is a generalization of the primal-dual gap that is commonly monitored in implementations of Dantzig–Wolfe decomposition for optimization models. Convergence is proved under conditions general enough to be applicable to many models. An illustration is provided for a two-region competitive model of Canadian energy markets. Copyright Springer Science + Business Media, Inc. 2005

Suggested Citation

  • J. Fuller & William Chung, 2005. "Dantzig—Wolfe Decomposition of Variational Inequalities," Computational Economics, Springer;Society for Computational Economics, vol. 25(4), pages 303-326, June.
  • Handle: RePEc:kap:compec:v:25:y:2005:i:4:p:303-326
    DOI: 10.1007/s10614-005-2519-x
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10614-005-2519-x
    Download Restriction: Access to full text is restricted to subscribers.

    File URL: https://libkey.io/10.1007/s10614-005-2519-x?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. B. S. He & L. Z. Liao & H. Yang, 1999. "Decomposition Method for a Class of Monotone Variational Inequality Problems," Journal of Optimization Theory and Applications, Springer, vol. 103(3), pages 603-622, December.
    2. Steven A. Gabriel & Andy S. Kydes & Peter Whitman, 2001. "The National Energy Modeling System: A Large-Scale Energy-Economic Equilibrium Model," Operations Research, INFORMS, vol. 49(1), pages 14-25, February.
    3. Chung, W. & Wu, Y. June & Fuller, J. David, 1997. "Dynamic energy and environment equilibrium model for the assessment of CO2 emission control in Canada and the USA," Energy Economics, Elsevier, vol. 19(1), pages 103-124, March.
    4. Frederic H. Murphy & Murthy V. Mudrageda, 1998. "A Decomposition Approach for a Class of Economic Equilibrium Models," Operations Research, INFORMS, vol. 46(3), pages 368-377, June.
    5. Wu, Y.June & Chung, William, 1997. "Assessing the control of energy-related CO2 emissions with a dynamic energy process model," Energy, Elsevier, vol. 22(7), pages 693-704.
    6. WEI, Jing-Yuan & SMEERS, Yves, 1999. "Spatial oligopolistic electricity models with Cournot generators and regulated transmission prices," LIDAM Reprints CORE 1454, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    7. Barton, Russell R. & Hearn, Donald W. & Lawphongpanich, Siriphong, 1989. "The equivalence of transfer and generalized benders decomposition methods for traffic assignment," Transportation Research Part B: Methodological, Elsevier, vol. 23(1), pages 61-73, February.
    8. Byong-Hun Ahn & William W. Hogan, 1982. "On Convergence of the PIES Algorithm for Computing Equilibria," Operations Research, INFORMS, vol. 30(2), pages 281-300, April.
    9. Bueler, Benno, 1997. "Solving an equilibrium model for trade of CO2 emission permits," European Journal of Operational Research, Elsevier, vol. 102(2), pages 393-403, October.
    10. Frederic H. Murphy, 1993. "Making Large-Scale Models Manageable: Modeling from an Operations Management Perspective," Operations Research, INFORMS, vol. 41(2), pages 241-252, April.
    11. Frederic H. Murphy, 1973. "Column Dropping Procedures for the Generalized Programming Algorithm," Management Science, INFORMS, vol. 19(11), pages 1310-1321, July.
    12. Frederic H. Murphy & John J. Conti & Susan H. Shaw & Reginald Sanders, 1988. "Modeling and Forecasting Energy Markets with the Intermediate Future Forecasting System," Operations Research, INFORMS, vol. 36(3), pages 406-420, 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. Fuller, J. David & Chung, William, 2008. "Benders decomposition for a class of variational inequalities," European Journal of Operational Research, Elsevier, vol. 185(1), pages 76-91, February.
    2. Egging, Ruud & Holz, Franziska, 2016. "Risks in global natural gas markets: Investment, hedging and trade," Energy Policy, Elsevier, vol. 94(C), pages 468-479.
    3. Egging, Ruud & Pichler, Alois & Kalvø, Øyvind Iversen & Walle–Hansen, Thomas Meyer, 2017. "Risk aversion in imperfect natural gas markets," European Journal of Operational Research, Elsevier, vol. 259(1), pages 367-383.
    4. Egging, Ruud, 2013. "Benders Decomposition for multi-stage stochastic mixed complementarity problems – Applied to a global natural gas market model," European Journal of Operational Research, Elsevier, vol. 226(2), pages 341-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. W. Chung & J. Fuller & Y. Wu, 2003. "A New Demand-Supply Decomposition Method for a Class of Economic Equilibrium Models," Computational Economics, Springer;Society for Computational Economics, vol. 21(3), pages 231-243, June.
    2. William Chung & J. D. Fuller & Y. June Wu, 2006. "A New Decomposition Method for Multiregional Economic Equilibrium Models," Operations Research, INFORMS, vol. 54(4), pages 643-655, August.
    3. William Chung & J. David Fuller, 2010. "Subproblem Approximation in Dantzig-Wolfe Decomposition of Variational Inequality Models with an Application to a Multicommodity Economic Equilibrium Model," Operations Research, INFORMS, vol. 58(5), pages 1318-1327, October.
    4. Fuller, J. David & Chung, William, 2008. "Benders decomposition for a class of variational inequalities," European Journal of Operational Research, Elsevier, vol. 185(1), pages 76-91, February.
    5. Wu, Y. June & Chung, William & Fuller, J. David, 2000. "Decomposing multi-regional dynamic energy process models," Applied Energy, Elsevier, vol. 66(3), pages 225-235, July.
    6. Steven A. Gabriel & Andy S. Kydes & Peter Whitman, 2001. "The National Energy Modeling System: A Large-Scale Energy-Economic Equilibrium Model," Operations Research, INFORMS, vol. 49(1), pages 14-25, February.
    7. Egging, Rudolf G. & Gabriel, Steven A., 2006. "Examining market power in the European natural gas market," Energy Policy, Elsevier, vol. 34(17), pages 2762-2778, November.
    8. William W. Hogan, 2002. "Energy Modeling for Policy Studies," Operations Research, INFORMS, vol. 50(1), pages 89-95, February.
    9. William Chung, 2024. "Truncated Dantzig–Wolfe Decomposition for a Class of Constrained Variational Inequality Problems," Computational Economics, Springer;Society for Computational Economics, vol. 64(1), pages 81-104, July.
    10. Gabriel, Steven A. & Zhuang, Jifang & Kiet, Supat, 2005. "A large-scale linear complementarity model of the North American natural gas market," Energy Economics, Elsevier, vol. 27(4), pages 639-665, July.
    11. Steven A. Gabriel & Supat Kiet & Jifang Zhuang, 2005. "A Mixed Complementarity-Based Equilibrium Model of Natural Gas Markets," Operations Research, INFORMS, vol. 53(5), pages 799-818, October.
    12. GABRIEL, Steven & SMEERS, Yves, 2005. "Complementarity problems in restructured natural gas markets," LIDAM Discussion Papers CORE 2005037, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    13. Wu, Y. June & Rosen, Marc A., 1999. "Assessing and optimizing the economic and environmental impacts of cogeneration/district energy systems using an energy equilibrium model," Applied Energy, Elsevier, vol. 62(3), pages 141-154, March.
    14. Kydes, Andy S., 2007. "Impacts of a renewable portfolio generation standard on US energy markets," Energy Policy, Elsevier, vol. 35(2), pages 809-814, February.
    15. Chung, William, 2002. "WWW-WATEMS-GDL: an internet modelling system for energy policy models," Energy, Elsevier, vol. 27(6), pages 569-577.
    16. Gabriel, Steven A. & Vikas, Shree & Ribar, David M., 2000. "Measuring the influence of Canadian carbon stabilization programs on natural gas exports to the United States via a 'bottom-up' intertemporal spatial price equilibrium model," Energy Economics, Elsevier, vol. 22(5), pages 497-525, October.
    17. Frederic H. Murphy & Murthy V. Mudrageda, 1998. "A Decomposition Approach for a Class of Economic Equilibrium Models," Operations Research, INFORMS, vol. 46(3), pages 368-377, June.
    18. Fernández, Mauricio & Muñoz, Francisco D. & Moreno, Rodrigo, 2020. "Analysis of imperfect competition in natural gas supply contracts for electric power generation: A closed-loop approach," Energy Economics, Elsevier, vol. 87(C).
    19. Melinda Hobbs & Michael Mellish & Frederic H. Murphy & Richard Newcombe & Reginald Sanders & Peter Whitman, 2001. "Rebuilding the Coal Model in the Energy Information Administration's National Energy Modeling System," Interfaces, INFORMS, vol. 31(5), pages 24-42, October.
    20. Benjamin F. Hobbs & Fieke A.M. Rijkers & Maroeska G. Boots, 2005. "The More Cooperation, The More Competition? A Cournot Analysis of the Benefits of Electric Market Coupling," The Energy Journal, International Association for Energy Economics, vol. 0(Number 4), pages 69-98.

    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:kap:compec:v:25:y:2005:i:4:p:303-326. 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.