Multiple Column Generation Algorithms for Variational Inequalities

Project: Research

View graph of relations


Column generation (CG) is a method to solve large-scale mathematical programming problems such as optimization models and variational inequalities (VI) involving a vast number of variables. These models can be found in multi-cloud systems, multicommodityeconomic equilibrium models, and transportation models. These models would become too large to be solved due to the rise of big data. For example, large-scale VI problems can be easily found in stochastic VI settings with large-scale scenario analysis.Even a well-established VI solver (PATH) has been found to terminate when attempting to solve a large-scale VI problem due to a lack of memory. By using column generation algorithms, such large-scale problems can be decomposed into smaller subproblems to besolved on several computers. Another motivation for using CG is to improve model development and maintenance efficiency by joining separately well-developed submodels when a converged solution is needed. CG involves solving a subproblem and a master problem iteratively. It is assumed that there are efficient solution methods to solve the subproblem and the master problem. However, it is well known that the CG algorithms converge rapidly at first but subsequently slowly, with a long tail of near-optimal solutions. As the final optimality gap cannot be closed, this long-tail convergence resulting in poor computational performance becomes a drawback. Other drawbacks are dual oscillations and primal degeneracy, and alternative dual optimal solutions in optimization models. In our experience, CG methods for VI problems inherit this long-tail convergence property. From the literature, three stabilization techniques of optimization models can be found to ease the above drawbacks. These techniques are the proximity of a stability center, smoothing techniques, and centralized prizes for stabilizing the iterative dual solutions from the master problems. It is worthwhile to explore the use of these three stabilization techniques for VI problems. Moreover, some methods of easing long-tail convergence with these stabilization techniques will be developed to enhance CG-VI's computational performance. According to the literature on applying CG to optimization models, the larger the number ofcolumns of the subproblem used to initialize the algorithm, the more quickly the solution can be found. Following this principle, we aim to develop a general method of solving multiple types of the subproblem (i.e., solving different kinds of the subproblem) in eachCG iteration. 


Project number9043417
Grant typeGRF
StatusNot started
Effective start/end date1/01/23 → …