A Penalized Sequential Convex Programming Approach for Continuous Network Design Problems

References

• Abdulaal M, LeBlanc LJ (1979) Continuous equilibrium network design models. Transportation Res. Part B: Methodological 13(1):19–32.Crossref, Google Scholar
• Ban JX, Liu HX, Ferris MC, Ran B (2006) A general MPCC model and its solution algorithm for continuous network design problem. Math. Comput. Model. 43(5–6):493–505.Crossref, Google Scholar
• Ben-Ayed O, Blair CE (1990) Computational difficulties of bilevel linear programming. Oper. Res. 38(3):556–560.Link, Google Scholar
• Bertsekas D (1999) Nonlinear Programming, 2nd ed. (Athena Scientific, Belmont, MA).Google Scholar
• Boyd S, Vandenberghe L (2004) Convex Optimization (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Byeon G, Van Hentenryck P (2022) Benders subproblem decomposition for bilevel problems with convex follower. INFORMS J. Comput. 34(3):1749–1767.Link, Google Scholar
• Chiou SW (2005) Bilevel programming for the continuous transport network design problem. Transportation Res. Part B: Methodological 39(4):361–383.Crossref, Google Scholar
• Chiou SW (2009) A subgradient optimization model for continuous road network design problem. Appl. Math. Model. 33(3):1386–1396.Crossref, Google Scholar
• Colson B, Marcotte P, Savard G (2007) An overview of bilevel optimization. Ann. Oper. Res. 153(1):235–256.Crossref, Google Scholar
• Dempe S (1992) A necessary and a sufficient optimality condition for bilevel programming problems. Optimization 25(4):341–354.Crossref, Google Scholar
• Dempe S (2003) Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints. Optimization 52(3):333–359.Crossref, Google Scholar
• Dempe S (2020) Bilevel optimization: Theory, algorithms, applications and a bibliography. Dempe S, Zemkoho A, eds. Bilevel Optimization: Advances and Next Challenges. Springer Optimization and Its Applications, vol. 161 (Springer, Cham, Switzerland), 581–672.Crossref, Google Scholar
• Dempe S, Mehlitz P (2024) Duality-based single-level reformulations of bilevel optimization problems. Preprint, submitted May 13, https://arxiv.org/abs/2405.07672.Google Scholar
• Di Lorenzo D, Galligari A, Sciandrone M (2015) A convergent and efficient decomposition method for the traffic assignment problem. Comput. Optim. Appl. 60(1):151–170.Crossref, Google Scholar
• Fiacco AV (1976) Sensitivity analysis for nonlinear programming using penalty methods. Math. Programming 10(1):287–311.Crossref, Google Scholar
• Fischer A, Zemkoho AB, Zhou S (2022) Semismooth Newton-type method for bilevel optimization: Global convergence and extensive numerical experiments. Optim. Methods Software 37(5):1770–1804.Crossref, Google Scholar
• Floudas CA (2013) Deterministic Global Optimization: Theory, Methods and Applications (Springer, New York).Google Scholar
• Friesz TL, Tobin RL, Cho HJ, Mehta NJ (1990) Sensitivity analysis based heuristic algorithms for mathematical programs with variational inequality constraints. Math. Programming 48(1):265–284.Crossref, Google Scholar
• Friesz TL, Cho HJ, Mehta NJ, Tobin RL, Anandalingam G (1992) A simulated annealing approach to the network design problem with variational inequality constraints. Transportation Sci. 26(1):18–26.Link, Google Scholar
• Fukushima M (1984) A modified Frank-Wolfe algorithm for solving the traffic assignment problem. Transportation Res. Part B: Methodological 18(2):169–177.Crossref, Google Scholar
• Gairing M, Harks T, Klimm M (2017) Complexity and approximation of the continuous network design problem. SIAM J. Optim. 27(3):1554–1582.Crossref, Google Scholar
• Gao LL, Ye J, Yin H, Zeng S, Zhang J (2022) Value function based difference-of-convex algorithm for bilevel hyperparameter selection problems. Chaudhuri K, Jegelka S, Song L, Szepesvari C, Niu G, Sabato S, eds. Proc. 39th Internat. Conf. Machine Learn. (JMLR.org, Baltimore), 7164–7182.Google Scholar
• Guo L, Yin H, Zhang J (2025) A penalized sequential convex programming approach for continuous network design problems. http://dx.doi.org/10.1287/ijoc.2024.0737.cd, https://github.com/INFORMSJoC/2024.0737.Google Scholar
• Kleinert T, Schmidt M (2021) Computing feasible points of bilevel problems with a penalty alternating direction method. INFORMS J. Comput. 33(1):198–215.Link, Google Scholar
• Labbé M, Marcotte P (2021) Bilevel network design. Crainic TG, Gendreau M, Gendron B, eds. Network Design with Applications to Transportation and Logistics (Springer, Cham, Switzerland), 255–281. Crossref, Google Scholar
• Le Thi HA, Pham Dinh T (2018) DC programming and DCA: Thirty years of developments. Math. Programming 169(1):5–68.Crossref, Google Scholar
• Le Thi HA, Huynh VN, Dinh TP (2014) DC programming and DCA for general DC programs. van Do T, Thi H, Nguyen N, eds. Advanced Computational Methods for Knowledge Engineering, Advances in Intelligent Systems and Computing, vol. 282 (Springer, Cham, Switzerland), 15–35.Crossref, Google Scholar
• Li C, Yang H, Zhu D, Meng Q (2012) A global optimization method for continuous network design problems. Transportation Res. Part B: Methodological 46(9):1144–1158.Crossref, Google Scholar
• Li J, Yu J, Liu B, Nie Y, Wang Z (2023) Achieving hierarchy-free approximation for bilevel programs with equilibrium constraints. Krause A, Brunskill E, Cho K, Engelhardt B, Sabato S, Scarlett J, eds. Proc. 40th Internat. Conf. Machine Learn. (JMLR.org, Honolulu, HI), 20312–20335.Google Scholar
• Lim AC (2002) Transportation Network Design Problems: An MPEC Approach (Johns Hopkins University, Baltimore).Google Scholar
• Lin GH, Xu M, Ye JJ (2014) On solving simple bilevel programs with a nonconvex lower level program. Math. Programming 144(1):277–305.Crossref, Google Scholar
• Liu H, Wang DZ (2015) Global optimization method for network design problem with stochastic user equilibrium. Transportation Res. Part B: Methodological 72(February):20–39.Crossref, Google Scholar
• Marcotte P (1983) Network optimization with continuous control parameters. Transportation Sci. 17(2):181–197.Link, Google Scholar
• Marcotte P (1986) Network design problem with congestion effects: A case of bilevel programming. Math. Programming 34(2):142–162.Crossref, Google Scholar
• Marcotte P, Marquis G (1992) Efficient implementation of heuristics for the continuous network design problem. Ann. Oper. Res. 34(1):163–176.Crossref, Google Scholar
• Meng Q, Yang H, Bell MG (2001) An equivalent continuously differentiable model and a locally convergent algorithm for the continuous network design problem. Transportation Res. Part B: Methodological 35(1):83–105.Crossref, Google Scholar
• Nie YM (2010) A class of bush-based algorithms for the traffic assignment problem. Transportation Res. Part B: Methodological 44(1):73–89.Crossref, Google Scholar
• Nocedal J, Wright SJ (1999) Numerical Optimization (Springer, New York).Crossref, Google Scholar
• Outrata JV (1990) On the numerical solution of a class of Stackelberg problems. Zeitschrift für Oper. Res. 34:255–277.Google Scholar
• Patwary AUZ, Wang S, Lo HK (2023) Iterative backpropagation method for efficient gradient estimation in bilevel network equilibrium optimization problems. Transportation Sci. 57(5):1134–1159.Link, Google Scholar
• Strekalovsky AS, Orlov AV, Malyshev AV (2010) On computational search for optimistic solutions in bilevel problems. J. Global Optim. 48(1):159–172.Crossref, Google Scholar
• Suwansirikul C, Friesz TL, Tobin RL (1987) Equilibrium decomposed optimization: A heuristic for the continuous equilibrium network design problem. Transportation Sci. 21(4):254–263.Link, Google Scholar
• Tin A, Zemkoho AB (2023) Levenberg-Marquardt method and partial exact penalty parameter selection in bilevel optimization. Optim. Engrg. 24(2):1343–1385.Crossref, Google Scholar
• Transportation Networks for Research Core Team (2023) Transportation networks for research. Accessed May 16, https://github.com/bstabler/TransportationNetworks.Google Scholar
• Tuy H (2000) Monotonic optimization: Problems and solution approaches. SIAM J. Optim. 11(2):464–494.Crossref, Google Scholar
• Tuy H, Ghannadan S (1998) A new branch and bound method for bilevel linear programs. Migdalas A, Pardalos PM, Värbrand P, eds. Multilevel Optimization: Algorithms and Applications (Springer, Boston), 231–249. Crossref, Google Scholar
• Tuy H, Migdalas A, Hoai-Phuong N (2007) A novel approach to bilevel nonlinear programming. J. Global Optim. 38:527–554.Crossref, Google Scholar
• von Stackelberg H (1934) Marktform Und Gleichgewicht (Julius Springer Verlag, Vienna, Austria).Google Scholar
• Wang DZ, Lo HK (2010) Global optimum of the linearized network design problem with equilibrium flows. Transportation Res. Part B: Methodological 44(4):482–492.Crossref, Google Scholar
• Wang J, He X, Peeta S, Wang W (2022) Globally convergent line search algorithm with Euler-based step size-determination method for continuous network design problem. Transportation Res. Part B: Methodological 163(September):119–144.Crossref, Google Scholar
• Wardrop JG (1952) Some theoretical aspects of road traffic research. Glanville W, Adams W, Bennett G, Green S, Bellamy D, Smeed R, Clayton A, Duff J, eds. Proc. Inst. Civil Engineers (Thomas Telford Ltd, London), 325–362.Google Scholar
• Xu Z, Xie J, Liu X, Nie Y (2022) Hyperbush algorithm for strategy-based equilibrium traffic assignment problems. Transportation Sci. 56(4):877–903.Link, Google Scholar
• Yang H, Bell MGH (1998) Models and algorithms for road network design: A review and some new developments. Transport Rev. 18(3):257–278.Crossref, Google Scholar
• Yang H, Huang HJ (2005) Mathematical and Economic Theory of Road Pricing (Elsevier, London).Crossref, Google Scholar
• Yang H, Yagar S (1995) Traffic assignment and signal control in saturated road networks. Transportation Res. Part A: Policy Practice 29(2):125–139.Crossref, Google Scholar
• Ye JJ, Zhu D (1995) Optimality conditions for bilevel programming problems. Optimization 33(1):9–27.Crossref, Google Scholar
• Ye JJ, Yuan X, Zeng S, Zhang J (2023) Difference of convex algorithms for bilevel programs with applications in hyperparameter selection. Math. Programming 198(2):1583–1616.Crossref, Google Scholar
• Yin Y (2000) Genetic-algorithms-based approach for bilevel programming models. J. Transportation Engrg. 126(2):115–120.Crossref, Google Scholar