Approximate Dantzig-wolfe Decomposition for Solving a Class of Variational Inequality Problems

Project: Research

View graph of relations


This proposed research aims to develop a new approximation method to apply Dantzig–Wolfe (DW) decomposition algorithm to a class of large-scale economic equilibrium modelin the form of variational inequality (VI) problems or mixed complementarity problems. Forinstance, the multicommodity economic equilibrium model is characterized by a cost-minimizinglinear programming model of the supply side and a vector-valued function thatgives demands as functions of the prices, which are equal to the marginal costs of supplyingdemands. Another example is the transportation models in VI formulation.A decomposition algorithm is used to ease model development and maintenance through asolution method that links separately well-developed submodels only when a global solutionis desired. Other possible benefits include the ability to solve a model on several computersthat is too large to be solved on a single computer. The approximation method aims toenhance the flexibility and the performance of the decomposition algorithm.As an integration tool, the decomposition method splits the original VI into two subproblems.The decomposed VI model consists of a master problem (master-VI) and a subproblem (sub-VI), which are equilibrium models. Sub-VI can be further decomposed by utilizing parallelcomputing and by shortening the solution time if it has a special structure, such as blockangular constraints.Two layers of computational sequences are used to solve the decomposed VI model. Theouter layer is the decomposition computational sequence, in which the master-VI and thesub-VI are solved in an iterative manner. The inner layer within each iteration of thedecomposition method consists of two computational sequences, which are the solutionmethods to solve master-VI and sub-VI individually. These solution methods for VI existbecause they apply a sequence solution method (of constrained optimization problems) tosolve the VI in an iterative manner. In short, we have one outer computational sequence fordecomposition method and two inner computational sequences for two VI problems withineach decomposition iteration.Solving both master-VI and sub-VI approximately in a way that the original VI solution canstill be solved is ideal. We can find sub-VI approximation method and master-VIapproximation method from the literature. However, a study on the integration of bothapproximation methods does not exist because of the different convergence properties of DWalgorithm and of the solution methods for VIs. In the proposed work, a general approximate-DW method for VI is developed to remove one of the layers of computational sequences bycombining DW decomposition method and the solution methods for VIs. The convergenceproperties of the new method are studied, and the empirical tests of the new method areincluded.?


Project number9042415
Grant typeGRF
Effective start/end date1/01/1719/08/19

    Research areas

  • Large-scale , Decomposition algorithm , Variational inequalities , Approximation methods ,