Truncated Dantzig-Wolfe Decomposition for a Class of Constrained Variational Inequality Problems

In this paper, we discuss how to use the Dantzig-Wolfe (DW) decomposition method to solve a class of constrained variational inequality (VI) problems. These problems include multi-regional energy equilibrium models with linking constraints or nonlinear multicommodity network flow problems with asymmetric cost functions and side constraints. The decomposed VI problem has a subproblem which is a constrained optimisation problem consisting of all structural constraints. The resulting master problem is a VI problem with dummy linking constraints. The size of the master problem is much smaller than that of the original constrained VI problem. If the subproblem comprises the constraint set with a special structure, such as block-angular structure, it can be further decomposed by the DW decomposition method (nested DW). We find that by performing an iteration of the nested DW decomposition on the subproblem (truncated DW), we can obtain an equilibrium solution. The efficiency of this truncated DW may depend on the VI problems. Theoretical analysis indicated that the algorithm is guaranteed to converge under some assumptions. Illustrative examples are given. From the results of the examples, we find that moving the linking constraints of the structural constraints back from the subproblem to the master problem may worsen the computational performance.

Automated summary

This paper discusses the use of the Dantzig-Wolfe (DW) decomposition method for solving a class of constrained variational inequality (VI) problems. The decomposed VI problem includes a subproblem consisting of all structural constraints, and a master problem with dummy linking constraints. The efficiency of the method depends on the specific VI problems.