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

• 成果类型: Article
• 署名作者: Chung, William; Fuller, J. David
• 署名单位: City University of Hong Kong; University of Waterloo
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1090.0803
• 发表日期: 2010
• 页码: 1318-1327
• 关键词: algorithm

摘要

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.