Simplicial decomposition (SD) of variational inequalities experiences the long-tail convergence property. That is, the equilibrium solution rapidly progresses at first but then tails off, making only a tiny amount of progress per column generation iteration, which is a drawback of SD-VI. In the context of Dantzig-Wolfe of LP, it is reported that the more proposals are used to initialize the algorithm, the faster the solution can be found by reducing the number of decomposition steps. Therefore, I proposed to solve multiple nonlinear column generation (mNCG) subproblems in each SD-VI iteration (SD-VI-mNCG) instead of solving only one subproblem as in SD-VI. Generating multiple column generation subproblem solutions in each SD-VI iteration enabled the corresponding convex hull to be rapidly enlarged. Consequently, the number of SD-VI iterations could be greatly reduced. A transportation network equilibrium problem was used to study the performance of the SD-VI-mNCG.
Citation: William Chung. Simplicial decomposition of variational inequalities with multiple nonlinear column generation[J]. AIMS Mathematics, 2024, 9(6): 14618-14639. doi: 10.3934/math.2024711
Simplicial decomposition (SD) of variational inequalities experiences the long-tail convergence property. That is, the equilibrium solution rapidly progresses at first but then tails off, making only a tiny amount of progress per column generation iteration, which is a drawback of SD-VI. In the context of Dantzig-Wolfe of LP, it is reported that the more proposals are used to initialize the algorithm, the faster the solution can be found by reducing the number of decomposition steps. Therefore, I proposed to solve multiple nonlinear column generation (mNCG) subproblems in each SD-VI iteration (SD-VI-mNCG) instead of solving only one subproblem as in SD-VI. Generating multiple column generation subproblem solutions in each SD-VI iteration enabled the corresponding convex hull to be rapidly enlarged. Consequently, the number of SD-VI iterations could be greatly reduced. A transportation network equilibrium problem was used to study the performance of the SD-VI-mNCG.
| [1] |
E. Çelebi, J. David Fuller, Master problem approximations in Dantzig-Wolfe decomposition of variational inequality problems with applications to two energy market models, Comput. Oper. Res., 40 (2013), 2724–2739. https://doi.org/10.1016/j.cor.2013.05.012 doi: 10.1016/j.cor.2013.05.012
|
| [2] |
F. Murphy, A. Pierru, Y. Smeers, A tutorial on building policy models as mixed-complementarity problems, Interfaces, 46 (2016), 465–481. https://doi.org/10.1287/inte.2016.0842 doi: 10.1287/inte.2016.0842
|
| [3] |
W. Chung, Approximate Dantzig-Wolfe decomposition to solve a class of variational inequality problems with an illustrative application to electricity market models, Expert Syst. Appl., 118 (2019), 140–151. https://doi.org/10.1016/j.eswa.2018.09.043 doi: 10.1016/j.eswa.2018.09.043
|
| [4] |
E. Bettiol, L. Létocart, F. Rinaldi, E. Traversi, A conjugate direction based simplicial decomposition framework for solving a specific class of dense convex quadratic programs, Comput. Optim. Appl., 75 (2020), 321–360. https://doi.org/10.1007/s10589-019-00151-4 doi: 10.1007/s10589-019-00151-4
|
| [5] |
D. Uciński, Construction of constrained experimental designs on finite spaces for a modified E-optimality criterion, Int. J. Appl. Math. Comp., 30 (2020), 659–677. https://doi.org/10.34768/amcs-2020-0049 doi: 10.34768/amcs-2020-0049
|
| [6] |
M. Guignard, A. Ahlatcioglu, The convex hull heuristic for nonlinear integer programming problems with linear constraints and application to quadratic 0–1 problems, J. Heuristics, 27 (2021), 251–265. https://doi.org/10.1007/s10732-019-09433-w doi: 10.1007/s10732-019-09433-w
|
| [7] |
P. Delle Site, Pricing of connected and autonomous vehicles in mixed-traffic networks, Transport. Res. Rec., 2675 (2021), 178–192. https://doi.org/10.1177/0361198120985850 doi: 10.1177/0361198120985850
|
| [8] |
M. Morabit, G. Desaulniers, A. Lodi, Machine-learning-based column selection for column generation, Transport. Sci., 55 (2021), 815–831. https://doi.org/10.1287/trsc.2021.1045 doi: 10.1287/trsc.2021.1045
|
| [9] |
L. Nazareth, Numerical behavior of LP algorithms based upon the decomposition principle, Linear Algebra Appl., 57 (1984), 181–189. https://doi.org/10.1016/0024-3795(84)90186-1 doi: 10.1016/0024-3795(84)90186-1
|
| [10] | J. Nazareth, Computer solution of linear programs, New York: Oxford University Press, 1987. |
| [11] |
J. Ho, Convergence behavior of decomposition algorithms for linear programs, Oper. Res. Lett., 3 (1984), 91–94. https://doi.org/10.1016/0167-6377(84)90048-8 doi: 10.1016/0167-6377(84)90048-8
|
| [12] |
M. Lübbecke, J. Desrosiers, Selected topics in column generation, Oper. Res., 53 (2005), 1007–1023. https://doi.org/10.1287/opre.1050.0234 doi: 10.1287/opre.1050.0234
|
| [13] | G. Dantzig, Linear programming and extensions, Santa Monica: RAND Corporation, 1963. https://doi.org/10.7249/R366 |
| [14] |
E. Beale, P. Hughes, R. Small, Experiences in using a decomposition program, Comput. J., 8 (1965), 13–18. https://doi.org/10.1093/comjnl/8.1.13 doi: 10.1093/comjnl/8.1.13
|
| [15] |
F. Murphy, Column dropping procedures for the generalized programming algorithm, Manage. Sci., 19 (1973), 1310–1321. https://doi.org/10.1287/mnsc.19.11.1310 doi: 10.1287/mnsc.19.11.1310
|
| [16] |
R. O'Neill, Technical note-column dropping in the Dantzig-Wolfe convex programming algorithm: computational experience, Oper. Res., 25 (1977), 148–155. https://doi.org/10.1287/opre.25.1.148 doi: 10.1287/opre.25.1.148
|
| [17] |
R. Marsten, W. Hogan, J. Blankenship, The boxstep method for Large-scale optimization, Oper. Res., 23 (1975), 389–405. https://doi.org/10.1287/opre.23.3.389 doi: 10.1287/opre.23.3.389
|
| [18] |
T. Larsson, M. Patriksson, Simplicial decomposition with disaggregated representation for the traffic assignment problem, Transport. Sci., 26 (1992), 4–17. https://doi.org/10.1287/trsc.26.1.4 doi: 10.1287/trsc.26.1.4
|
| [19] |
W. Chung, J. Fuller, Y. Wu, A new decomposition method for multiregional economic equilibrium models, Oper. Res., 54 (2006), 643–655. https://doi.org/10.1287/opre.1060.0274 doi: 10.1287/opre.1060.0274
|
| [20] |
W. Chung, J. David Fuller, Subproblem approximation in Dantzig-Wolfe decomposition of variational inequality models with an application to a multicommodity economic equilibrium model, Oper. Res., 58 (2010), 1318–1327. https://doi.org/10.1287/opre.1090.0803 doi: 10.1287/opre.1090.0803
|
| [21] | W. Chung, Truncated Dantzig-Wolfe decomposition for a class of constrained variational inequality problems, Comput. Econ., in press. https://doi.org/10.1007/s10614-023-10422-2 |
| [22] |
M. Morabit, G. Desaulniers, A. Lodi, Machine-learning-based arc selection for constrained shortest path problems in column generation, INFORMS Journal on Optimization, 5 (2022), 191–210. https://doi.org/10.1287/ijoo.2022.0082 doi: 10.1287/ijoo.2022.0082
|
| [23] |
S. Kraul, M. Seizinger, J. Brunner, Machine learning–supported prediction of dual variables for the cutting stock problem with an application in stabilized column generation, INFORMS J. Comput., 35 (2023), 692–709. https://doi.org/10.1287/ijoc.2023.1277 doi: 10.1287/ijoc.2023.1277
|
| [24] | Y. Dirickx, L. Jennergren, Systems analysis by multilevel methods, New York: Wiley, 1979. |
| [25] |
P. Harker, J. Pang, Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications, Math. Program., 48 (1990), 161–220. (1990). https://doi.org/10.1007/BF01582255 doi: 10.1007/BF01582255
|
| [26] |
S. Lawphongpanich, D. Hearn, Simplical decomposition of the asymmetric traffic assignment problem, Transport. Res. B-Meth., 18 (1984), 123–133. https://doi.org/10.1016/0191-2615(84)90026-2 doi: 10.1016/0191-2615(84)90026-2
|
| [27] |
J. David Fuller, W. Chung, Dantzig-Wolfe decomposition of variational inequalities, Comput. Econ., 25 (2005), 303–326. https://doi.org/10.1007/s10614-005-2519-x doi: 10.1007/s10614-005-2519-x
|
| [28] | T. Larsson, M. Patriksson, C. Rydergren, Applications of simplicial decomposition with nonlinear column generation to nonlinear network flows, In: Network optimization, Berlin: Springer, 1997,346–373. https://doi.org/10.1007/978-3-642-59179-2_17 |
| [29] |
S. Dafermos, Relaxation algorithms for the general asymmetric traffic equilibrium problem, Transport. Sci., 16 (1982), 231–240. https://doi.org/10.1287/trsc.16.2.231 doi: 10.1287/trsc.16.2.231
|
| [30] |
A. Nagurney, K. Dhanda, Marketable pollution permits in oligopolistic markets with transaction costs, Oper. Res., 48 (2000), 424–435. https://doi.org/10.1287/opre.48.3.424.12429 doi: 10.1287/opre.48.3.424.12429
|
| [31] | S. Sharma, Q. Li, W. Wei, An enhanced SD-GS-AL algorithm for coordinating the optimal power and traffic flows with EVs, IEEE Trans. Smart Grid, in press. https://doi.org/10.1109/TSG.2024.3358805 |
| [32] |
Z. Wang, G. Li, Y. Xiao, S. Tang, M. Teng, A parallel decentralized solution for multi-regional unit commitment with convex AC power flow constraints, Proceedings of 7th Asia Conference on Power and Electrical Engineering (ACPEE), 2022, 1364–1373. https://doi.org/10.1109/ACPEE53904.2022.9783909 doi: 10.1109/ACPEE53904.2022.9783909
|
William Chung. Simplicial decomposition of variational inequalities with multiple nonlinear column generation[J]. AIMS Mathematics, 2024, 9(6): 14618-14639. doi: 10.3934/math.2024711
DownLoad: