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

Subproblem Approximation in Dantzig-Wolfe Decomposition of Variational Inequality Models with an Application to a Multicommodity Economic Equilibrium Model

Author

Listed:
  • William Chung

    (Department of Management Sciences, City University of Hong Kong, Hong Kong, China)

  • J. David Fuller

    (Department of Management Sciences, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada)

Abstract

We present a modification to Dantzig-Wolfe decomposition of variational inequality (VI) problems that allows for approximation of the VI mapping in the subproblem. The approximation is parameterized by the most recent master problem solution, and it must satisfy two simple requirements. In an electronic companion (online appendix), we show that the proofs of convergence and other important properties go through with subproblem approximation. The approximation procedure is illustrated by an application to a class of multicommodity economic equilibrium models (MCEEMs): the standard Dantzig-Wolfe decomposition by commodity does not allow the subproblem to be decomposed into separate subproblems for each commodity, but we show two ways to approximate the subproblem's inverse demand function, and both ways allow the subproblem to be broken into separate single-commodity problems. A further approximation is combined with each of the inverse demand approximations; in effect, an approximate supply or demand curve is introduced into each commodity's subproblem for transfers of commodities between different subproblems, thus allowing the subproblems to produce better proposals. An illustration is included for an MCEEM that represents energy markets in Canada.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:oropre:v:58:y:2010:i:5:p:1318-1327
    DOI: 10.1287/opre.1090.0803
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1090.0803
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1090.0803?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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. Frederic H. Murphy, 1973. "Column Dropping Procedures for the Generalized Programming Algorithm," Management Science, INFORMS, vol. 19(11), pages 1310-1321, July.
    6. 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. Juan Pablo Luna & Claudia Sagastizábal & Mikhail Solodov, 2020. "A class of Benders decomposition methods for variational inequalities," Computational Optimization and Applications, Springer, vol. 76(3), pages 935-959, July.
    2. Pedro Borges & Claudia Sagastizábal & Mikhail Solodov, 2021. "Decomposition Algorithms for Some Deterministic and Two-Stage Stochastic Single-Leader Multi-Follower Games," Computational Optimization and Applications, Springer, vol. 78(3), pages 675-704, April.

    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. William W. Hogan, 2002. "Energy Modeling for Policy Studies," Operations Research, INFORMS, vol. 50(1), pages 89-95, February.
    9. 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.
    10. 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).
    11. Chung, William, 2002. "WWW-WATEMS-GDL: an internet modelling system for energy policy models," Energy, Elsevier, vol. 27(6), pages 569-577.
    12. 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.
    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. 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.
    15. Matar, Walid & Murphy, Frederic & Pierru, Axel & Rioux, Bertrand, 2015. "Lowering Saudi Arabia's fuel consumption and energy system costs without increasing end consumer prices," Energy Economics, Elsevier, vol. 49(C), pages 558-569.
    16. Alejandro Jofré & R. Terry Rockafellar & Roger J-B. Wets, 2007. "Variational Inequalities and Economic Equilibrium," Mathematics of Operations Research, INFORMS, vol. 32(1), pages 32-50, February.
    17. De Jonghe, C. & Hobbs, B. F. & Belmans, R., 2011. "Integrating short-term demand response into long-term investment planning," Cambridge Working Papers in Economics 1132, Faculty of Economics, University of Cambridge.
    18. Frederic Murphy & Axel Pierru & Yves Smeers, 2016. "A Tutorial on Building Policy Models as Mixed-Complementarity Problems," Interfaces, INFORMS, vol. 46(6), pages 465-481, December.
    19. Murthy V. Mudrageda & Frederic H. Murphy & Steve Welch, 2004. "Developing Strategies for Maritrans’ Business Units," Interfaces, INFORMS, vol. 34(2), pages 149-161, April.
    20. Frederic H. Murphy & Zhong Xian Wang, 1993. "A network reformulation of an electric utility expansion planning model," Naval Research Logistics (NRL), John Wiley & Sons, vol. 40(4), pages 451-457, 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:58:y:2010:i:5:p:1318-1327. 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.