Benders decomposition for a class of variational inequalities
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
Original language | English |
---|---|
Pages (from-to) | 76-91 |
Journal / Publication | European Journal of Operational Research |
Volume | 185 |
Issue number | 1 |
Publication status | Published - 16 Feb 2008 |
Link(s)
Abstract
This paper examines Benders decomposition for a useful class of variational inequality (VI) problems that can model, e.g., economic equilibrium, games or traffic equilibrium. The dual of the given VI is defined. Benders decomposition of the original VI is derived by applying a Dantzig-Wolfe decomposition procedure to the dual of the given VI, and converting the dual forms of the Dantzig-Wolfe master and subproblems to their primal forms. The master problem VI includes a new cut at each iteration, with information from the latest subproblem VI, which is solved by fixing the "difficult" variables at values determined by the previous master problem. A scalar parameter called the convergence gap is calculated at each iteration; a negative value is equivalent to the algorithm making progress in that the last master problem solution is made infeasible by the new cut. Under mild conditions, the convergence gap approaches zero in the limit of many iterations. With a more restrictive condition that still admits many useful models, a zero value of the convergence gap implies that the master problem has found a solution of the VI. A small model of competitive equilibrium of three commodities in two regions serves as an illustration. © 2007 Elsevier B.V. All rights reserved.
Research Area(s)
- Benders decomposition, Equilibrium models, Variational inequality problems
Citation Format(s)
Benders decomposition for a class of variational inequalities. / Fuller, J. David; Chung, William.
In: European Journal of Operational Research, Vol. 185, No. 1, 16.02.2008, p. 76-91.
In: European Journal of Operational Research, Vol. 185, No. 1, 16.02.2008, p. 76-91.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review