Pith. sign in

REVIEW 3 major objections 4 minor 70 references

A Cardinality-Constrained Approach to Combinatorial Bilevel Congestion Pricing

T0 review · 3 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims that the combinatorial bilevel congestion pricing problem—choosing both toll locations and toll levels when travelers respond selfishly—can be reformulated without integer variables and solved by a penalized…

desk verdict A genuinely clever cardinality-constraint formulation with strong numerics, but the advertised convergence guarantee is proved only for an idealized exact-subproblem version, not for the tolerance-based implementation. read the letter →

arxiv 2412.06482 v3 pith:72RTEBEL submitted 2024-12-09 math.OC cs.GTcs.SYeess.SY

Lei Guo , Jiayang Li , Yu Marco Nie , Jun Xie This is my paper · ORCID
classification math.OCcs.GTcs.SYeess.SY MSC 90C2690C2790C3090C3590C46
keywords combinatorialbilevelcongestionpricingcardinalityconstrainttolllocationoptimizationKKTstationaritytrafficassignmentvaluefunctionreformulation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper takes a problem long considered intractable—choosing which roads to toll and how much to charge, knowing travelers will react selfishly—and claims it can be solved at realistic network scale with a convergence guarantee. The key move is to replace binary toll-location variables with a cardinality constraint that simply caps the number of nonzero tolls, then rewrite the travelers' equilibrium response as a gap-function constraint in a single-level program. A penalized block-coordinate algorithm splits that program into two tractable pieces, one of which is just a closed-form projection onto the cardinality constraint, and the paper proves the algorithm converges to an approximate KKT point. On a 2,950-link Chicago test network the method finishes in about 20 minutes, and on small benchmark networks it matches brute-force global optima.

What carries the argument

The load-bearing object is the pair formed by the cardinality constraint $|\mathrm{supp}(u)| \leq \kappa$, which replaces all binary toll-selection variables, and the gap function $f(u,v)-V(u)$, which encodes the travelers' user-equilibrium response as a single inequality. Under the paper's Assumption 1, the lower-level value function $V(u)$ is concave and continuously differentiable with gradient equal to the unique equilibrium flow, so the gap function is convex in $u$ for fixed $v$ and convex in $v$ for fixed $u$. The penalty approximation of the reformulated problem splits into a $u$-subproblem with a closed-form solution—project onto $U_\kappa$ by keeping the $\kappa$ largest $|z_a|$—a $v$-subproblem that is a standard convex traffic assignment, and a strongly convex $z$-subproblem over a box. The outer loop raises the penalty parameters until approximate feasibility holds, and Theorem 3 certifies the output satisfies the $\varepsilon$-approximate KKT conditions (23).

What would settle it

Take a small test network such as the Section 6.1 benchmark, replace the separable BPR travel time with one where each link's cost includes a term from a neighboring link's flow, and run PBCD; if the algorithm fails to drive both $f(z,v)-V(z)$ and $\|u-z\|$ below the prescribed $\varepsilon$, or if the computed lower-level value function stops being concave, that observation would falsify the Assumption-1 dependence of the convergence theorem.

Watch

Extended reading notes

Core claim

The central claim is that the combinatorial bilevel congestion pricing problem does not require integer variables to be solved at scale. Encoding the toll-location budget as $|\mathrm{supp}(u)| \leq \kappa$ turns the bilevel program into a single-level nonlinear program whose only discontinuous, non-convex piece is the cardinality constraint. That piece becomes tame because the projection onto the constraint has a closed form—keep the $\kappa$ links with the largest current toll magnitudes and zero the rest—and because, under separable convex travel times, the lower-level value function $V(u)$ is concave with the unique user-equilibrium flow as its gradient, making the gap function $f(u,v)-V(u)$ block-wise convex in $u$ and $v$. The paper proves that the penalized block-coordinate descent (PBCD) algorithm converges, after enough outer iterations, to an $\varepsilon$-approximate KKT point of the original problem, and reports that this solves a Chicago-Sketch network with 2,950 links in about 20 minutes.

Load-bearing premise

The entire algorithm rests on Assumption 1: every road's travel time depends only on its own traffic, is smoothly increasing, and is convex; the paper itself states that cross-link interactions would violate this and collapse the convergence guarantee.

Editorial extensions

If this is right

  • Toll location and toll level can be optimized jointly at real-network scale, so a planner does not have to guess the toll-link set before optimizing charges.
  • The returned solution comes with a convergence guarantee to an approximate stationary point, a quality assurance that the paper argues no earlier CBCP heuristic provides.
  • On the small benchmark network the algorithm consistently reproduces the brute-force global optimum and the known minimum-toll-location solution, and it can find alternative toll sets with the same total travel time.
  • On Chicago-Sketch the method shows strongly diminishing returns: roughly 500 toll links capture most of the achievable congestion reduction, and raising the budget to 1,600 adds little.
  • The algorithm runs in 18.5–23.7 minutes on the 2,950-link Chicago-Sketch network across all tested toll budgets $\kappa$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the same decomposition is tried on other mixed network design problems, the concavity of the lower-level value function is the bottleneck; the paper itself notes capacity expansion generally fails this test, so a natural extension is to seek relaxations that recover block convexity.
  • The closed-form projection onto the cardinality constraint suggests a transferable recipe: any bilevel problem with a concave lower-level value function could replace binary choices with a cardinality constraint and inherit a similar two-block penalty decomposition, e.g., in facility location or network interdiction models with congestion.
  • Because only the initial toll vector needs retuning in practice, a systematic study of how the limit point depends on the starting tolls, such as multi-start or warm-start strategies, could turn the local guarantee into a more robust planning tool.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. This paper considers the combinatorial bilevel congestion pricing (CBCP) problem, in which a leader selects both the set of toll links (of cardinality at most κ) and the toll levels, while travelers respond according to user equilibrium. The authors replace binary toll-location variables with a cardinality constraint, reformulate the lower-level equilibrium condition through a value-function gap, and introduce an auxiliary variable z coupled to the toll vector u by an equality constraint. Penalizing the gap and the equality yields a block-separable single-level problem, solved by a two-loop PBCD method: an inner block-coordinate-descent loop alternates between projection onto the cardinality set, a convex traffic assignment, and a strongly convex z-step; an outer loop increases the penalty parameters. The paper proves that the inner BCD converges to KKT points of the penalized problem and states Theorems 2 and 3 giving ε-optimal and ε-approximate-KKT guarantees for the outer loop. Numerical experiments on Hearn, Sioux-Falls, and Chicago-Sketch networks report wall-clock times under about 24 minutes for networks with up to 2,950 links, with small-network results matching brute-force global optima.

Significance. If the convergence guarantees were established for the implemented algorithm, this would be a significant methodological contribution: it replaces a mixed-integer bilevel formulation by a continuous cardinality-constrained formulation, exploits closed-form projection, and delivers a scalable algorithm with a stationarity guarantee, supported by credible small-network validation against brute-force enumeration and by sizeable improvements over link-ranking heuristics on larger networks. The paper also provides complete proofs in the appendix and detailed experiments on standard benchmark networks. However, the advertised guarantee is currently proved only under exact inner-solve assumptions that the implementation does not enforce, and the implemented stopping criteria do not verify the conditions asserted in the main theorem. As a result, the headline claim that the algorithm used to produce the reported timings converges to an approximate KKT point is not yet supported.

major comments (3)
  1. [Appendix A.5 / Theorem 3] The proof of Theorem 3 asserts that the returned point (uk, zk, vk) satisfies inequalities (35) and (36), citing equations (30)-(31) from the proof of Theorem 1. Those equations are established only for an accumulation point of the infinite BCD sequence, after passing to a subsequence, and they do not hold at each finite iterate. Moreover, Algorithm 1's Step (2) stops on an unspecified "approximate KKT stationary solution" criterion, and the numerical implementation stops the inner projected-gradient solver with the fixed tolerance ||PU(zk - ∇g(zk)) - zk|| ≤ 10^{-3} (Algorithm 3) and the outer loop with the relative tolerances ε1 = 10^{-4}, ε2 = 10^{-3} (Section 6), none of which verifies the KKT inclusions (23). The convergence guarantee in the abstract and Section 7 is therefore not established for the algorithm whose timings are reported. A revision should either provide a finite-time error analysis for the inner solver with an explicit stopping rule that certifies (23), or state Theorem 3 under an exact inner-oracle assumption and clearly label the implemented version as heuristic.
  2. [Theorem 1 / Theorem 3] The proof of Theorem 3 also requires a property stronger than KKT stationarity of the penalized problem (PAρ). Inequalities (35) and (36) assert that (uk, zk, vk) is a global minimizer of Φρk over the block (u,v) for fixed zk and over the block z for fixed (uk,vk). Theorem 1 only establishes KKT stationarity of an accumulation point, which for a nonconvex problem does not imply block-wise global optimality. Consequently, even an exact infinite execution of Algorithm 1 does not, without additional argument, justify the stationarity part of (23) for the stopping iterate. The authors should derive the approximate KKT inclusions directly from the residual of an inner termination test, or impose an explicit block-optimality condition at termination.
  3. [Section 6 / Step (2) of Algorithm 2] The implemented outer-loop stopping criterion uses relative errors, whereas Theorem 3's conclusion (23) requires the absolute inequalities f(zk, vk) - V(zk) ≤ ε and ||uk - zk|| ≤ ε. The conditions f(zk, vk)/max{f(zk, vk), 1} ≤ ε1 and ||uk - zk||/max{||uk||, 1} ≤ ε2 do not imply the absolute conditions unless the relevant quantities are bounded above by 1, which is not shown. Thus even if the inner solver were exact, the implemented stopping rule does not certify the approximate feasibility demanded by Theorem 3. The authors should either adapt the theorem to relative residuals or change the stopping criteria to match the absolute conditions in (23).
minor comments (4)
  1. [Section 5.1, Theorem 1, Eq. (19)] The right-hand side of inequality (19) reads min_{u∈Uκ, v∈Ω} Φρ(u, z1, v), but the proof establishes the inequality with zr in place of z1; the statement with z1 does not follow from equation (25). This appears to be a typo and should be corrected.
  2. [Section 7] The word "seperability" in the concluding remarks should be "separability."
  3. [Appendix B] The text says "for its implementation, visit this GitHub repository" but no URL is given; if the implementation is meant to be publicly available, a working link should be provided.
  4. [Abstract / Section 7] The abstract and concluding remarks state the convergence guarantee without restating the scope condition of Assumption 1 (separable, convex link travel times). Adding a qualifier such as "for separable link travel time functions" would align the headline claim with the limitation acknowledged in Section 7.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the convergence analysis is self-contained and parameter-free.

full rationale

I walked the derivation chain from the single-level reformulation (7) through the penalty approximation (10), the block decomposition (13)-(17), and the convergence theorems. Proposition 1 is proved in Appendix A from Assumption 1 and Danskin's theorem; the appended sentence 'The results can follow from Guo et al. (2024)' is a bibliographic aside, not the argument, so the co-authored citation is not load-bearing. Proposition 2 is proved elementarily and gives the closed-form projection (12). Theorems 1-3 contain no fitted constants: the iteration bounds (20) and (22) are explicit functions of the penalty multipliers, and the approximate-KKT conditions (23) are derived by Fermat's rule from the block optimality inequalities (35)-(36). Numerical validation is anchored externally to the Hearn-Ramana MTL solution and to Harks et al. heuristics, so the reported improvements are not defined into existence. Two limitations are real but not circular: Section 7 correctly states that the method requires separable travel times and concavity of the marginal value function, and Theorem 3's proof relies on Algorithm 1 returning an exact block-optimal point while the implementation uses finite tolerances; the latter is an omitted-proof/rigor gap in the 20-minute scalability claim, not a circular reduction of the kind that would raise the circularity score.

Assumptions & free parameters 6 free parameters · 6 assumptions · 0 invented entities

The central claim rests on standard transportation modeling assumptions (Wardrop UE, separable BPR-like cost functions) and on classical tools from variational analysis (Danskin, Fermat, limiting normal cones). The only genuinely new mathematical object is the projection onto the cardinality set U_kappa, which is derived in closed form rather than postulated. No invented physical or economic entities are introduced. The algorithmic hyperparameters (gamma, epsilon, initial z) are chosen by hand and tuned to the test networks, but the convergence theorems hold for any positive values.

free parameters (6)
  • gamma1 = 1.8
    Penalty growth factor for the gap constraint, set by hand in Section 6; the theorem requires only gamma1 > 1.
  • gamma2 = 5.0
    Penalty growth factor for the coupling constraint ||u-z||^2, set by hand in Section 6; the theorem requires only gamma2 > 1.
  • epsilon1 = 0.0001
    Relative tolerance for the gap constraint in the outer-loop termination test (Section 6); chosen to balance precision and runtime.
  • epsilon2 = 0.001
    Relative tolerance for the coupling constraint in the outer-loop termination test (Section 6).
  • initial toll value z1_0 = 0 if kappa > 0.2|A|, else 1.0
    Rule of thumb adopted by trial-and-error (Section 6); affects the quality of the local solution found.
  • initial penalty vector rho1 = not reported
    Algorithm 2 requires rho1 > 0 but the numerical values used in the experiments are not stated, hurting reproducibility.
assumptions (6)
  • domain assumption Assumption 1: separable, continuously differentiable, strictly increasing, convex link travel time functions t(v).
    Used in Proposition 1 to obtain differentiability and concavity of V(u) and block convexity of the gap function, which make the z- and v-subproblems tractable. Stated in Section 3 and flagged in the conclusion as the key limitation.
  • domain assumption Fixed OD demand and Wardrop user equilibrium as the lower-level solution concept.
    The whole model and the gap-function reformulation (7) presuppose travelers minimize individual cost and reach UE; stated in Sections 3 and 4.
  • standard math The feasible region Omega is compact and nonempty; link flows are nonnegative.
    Needed for the value function V(u) to be finite, continuous, and attained, and for S(u) to be nonempty (Section 4).
  • standard math Danskin's theorem for differentiating the value function.
    Invoked in the proof of Proposition 1 to assert grad V(u) = S(u).
  • standard math Fermat's rule and limiting normal cone calculus (Rockafellar and Wets).
    Used in the proofs of Theorems 1 and 3 to characterize KKT stationarity of the penalty approximation problem.
  • domain assumption Strong convexity of the z-subproblem (17) due to the rho2*||z-u||^2 term and the box U.
    Ensures the projected gradient Algorithm 3 converges to the global solution of (17); depends on V being concave, which follows from Assumption 1.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Cardinality-Constrained Approach to Combinatorial Bilevel Congestion Pricing." pith.science (2026). https://pith.science/paper/72RTEBEL

@misc{pith2026241206482,
  author       = {Pith},
  title        = {Pith review of: A Cardinality-Constrained Approach to Combinatorial Bilevel Congestion Pricing},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/72RTEBEL}},
  note         = {Machine review of arXiv:2412.06482}
}
read the original abstract

Combinatorial bilevel congestion pricing (CBCP), a variant of the mixed (continuous/discrete) network design problems, seeks to minimize the total travel time experienced by all travelers in a road network, by strategically selecting toll locations and determining toll charges. Conventional wisdom suggests that these problems are intractable since they have to be formulated and solved with a significant number of integer variables. Here, we devise a scalable local algorithm for the CBCP problem that guarantees convergence to an approximate Karush-Kuhn-Tucker point. Our approach is novel in that it eliminates the use of integer variables altogether, instead introducing a cardinality constraint that limits the number of toll locations to a user-specified upper bound. The resulting bilevel program with the cardinality constraint is then transformed into a block-separable, single-level optimization problem that can be solved efficiently after penalization and decomposition. We are able to apply the algorithm to solve, in about 20 minutes, a CBCP instance with up to 3,000 links. To the best of our knowledge, no existing algorithm can solve CBCP problems at such a scale while providing any assurance of convergence.

Figures

Figures reproduced from arXiv: 2412.06482 by the authors.

Figure 1
Figure 1. Topology of the Hearn’s network. On each network, we run PBCD in various settings. In each test, the effectiveness of a tolling scheme obtained by our algorithm, denoted as u ∗ , is evaluated as follows. We first compute the UE link flow pattern v ∗ under the tolling scheme u ∗ . Then, F ∗ = F(v ∗ ), i.e., the total travel time induced by u ∗ , is compared with two reference points: (1) F so = F(v so), i.e., the tot… view at source ↗
Figure 2
Figure 2. Toll links selected by PBCD (Algorithm 2) and H1–H4 [PITH_FULL_IMAGE:figures/full_fig_p020_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

70 extracted references · 64 canonical work pages

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION format.url url empty "" url if FUNCTION article output.bibitem format.authors "author" output.check author format.key output output.year.check new.block format.title "title" output.check new.block crossref missing format.jour.vol output format.article.crossref output.nonnull format.pages output if ne...

  2. [2]

    , " * write output.state after.block = add.period write newline

    ENTRY address author booktitle chapter edition editor howpublished institution journal key month note number organization pages publisher school series title type url volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.all := #1 'mid.sentence := ...

  3. [3]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize " " * FUNCT...

  4. [4]

    and Small, K

    Arnott, R. and Small, K. (1994). The economics of traffic congestion. American Scientist , 82(5):446--455

    work page 1994

  5. [5]

    Aussel, D., Lasluisa, D., and Salas, D. (2024). Cardinality constraints in single-leader-multi-follower games. arXiv preprint arXiv:2403.19074

    work page Pith review arXiv 2024

  6. [6]

    Bar-Gera, H. (2010). Traffic assignment by paired alternative segments. Transportation Research Part B: Methodological , 44(8-9):1022--1046

    work page 2010

  7. [7]

    and Blair, C

    Ben-Ayed, O. and Blair, C. E. (1990). Computational difficulties of bilevel linear programming. Operations Research , 38(3):556--560

    work page 1990

  8. [8]

    W., and Ramana, M

    Bergendorff, P., Hearn, D. W., and Ramana, M. V. (1997). Congestion toll pricing of traffic networks. In Pardalos, P. M., Hearn, D. W., and Hager, W. W., editors, Network Optimization , pages 51--71. Springer

    work page 1997

Show all 70 references
  1. [9]

    and Shioda, R

    Bertsimas, D. and Shioda, R. (2009). Algorithm for cardinality-constrained quadratic optimization. Computational Optimization and Applications , 43(1):1--22

    2009

  2. [10]

    Bialas, W. F. and Karwan, M. H. (1984). Two-level linear programming. Management Science , 30(8):1004--1020

    1984

  3. [11]

    Bienstock, D. (1996). Computational study of a family of mixed-integer quadratic programming problems. Mathematical Programming , 74:121--140

    1996

  4. [12]

    and McGill, J

    Bracken, J. and McGill, J. T. (1973). Mathematical programs with optimization problems in the constraints. Operations Research , 21(1):37--44

    1973

  5. [13]

    Colson, B., Marcotte, P., and Savard, G. (2007). An overview of bilevel optimization. Annals of Operations Research , 153(1):235--256

    2007

  6. [14]

    and Lindsey, R

    De Palma, A. and Lindsey, R. (2011). Traffic congestion pricing methodologies and technologies. Transportation Research Part C: Emerging Technologies , 19(6):1377--1399

    2011

  7. [15]

    Dempe, S. (2003). Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints. Optimization , 52(3):333--359

    2003

  8. [16]

    Dial, R. B. (2006). A path-based user-equilibrium traffic assignment algorithm that obviates path storage and enumeration. Transportation Research Part B: Methodological , 40(10):917--936

    2006

  9. [17]

    Ekstr \"o m, J., Sumalee, A., and Lo, H. K. (2012). Optimizing toll locations and levels using a mixed integer linear approximation approach. Transportation Research Part B: Methodological , 46(7):834--854

    2012

  10. [18]

    Facchinei, F., Jiang, H., and Qi, L. (1999). A smoothing method for mathematical programs with equilibrium constraints. Mathematical Programming , 85(1):107

    1999

  11. [19]

    Falk, J. E. and Liu, J. (1995). On bilevel programming, Part I : General nonlinear cases. Mathematical Programming , 70:47--72

    1995

  12. [20]

    Fallah Tafti, M., Ghane, Y., and Mostafaeipour, A. (2018). Application of particle swarm optimization and genetic algorithm techniques to solve bi-level congestion pricing problems. International Journal of Transportation Engineering , 5(3):261--273

    2018

  13. [21]

    Ferrari, P. (1995). Road pricing and network equilibrium. Transportation Research Part B: Methodological , 29(5):357--372

    1995

  14. [22]

    Ferrari, P. (2002). Road network toll pricing and social welfare. Transportation Research Part B: Methodological , 36(5):471--483

    2002

  15. [23]

    and Li, D

    Gao, J. and Li, D. (2013). Optimal cardinality constrained portfolio selection. Operations Research , 61(3):745--761

    2013

  16. [24]

    and Chen, X

    Guo, L. and Chen, X. (2021). Mathematical programs with complementarity constraints and a non- L ipschitz objective: Optimality and approximation. Mathematical Programming , 185(1):455--485

    2021

  17. [25]

    and Li, G

    Guo, L. and Li, G. (2024). Approximation methods for a class of non- L ipschitz mathematical programs with equilibrium constraints. Journal of Optimization Theory and Applications , 202(3):1421--1445

    2024

  18. [26]

    Guo, L., Zhou, W., Wang, X., Yang, H., and Fan, T. (2024). Penalty decomposition methods for second-best congestion pricing problems on large-scale networks. INFORMS Journal on Computing , (in press)

    2024

  19. [27]

    Harks, T., Kleinert, I., Klimm, M., and M \"o hring, R. H. (2015). Computing network tolls with support constraints. Networks , 65(3):262--285

    2015

  20. [28]

    Hearn, D. W. and Ramana, M. V. (1998). Solving congestion toll pricing models. In Marcotte, P. and Nguyen, S., editors, Equilibrium and Advanced Transportation Modelling , pages 109--124. Springer

    1998

  21. [29]

    Hoheisel, T., Kanzow, C., and Schwartz, A. (2013). Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints. Mathematical Programming , 137(1-2):257--288

    2013

  22. [30]

    Hu, X. M. and Ralph, D. (2004). Convergence of a penalty method for mathematical programming with complementarity constraints. Journal of Optimization Theory and Applications , 123:365--390

    2004

  23. [31]

    F., Solodov, M

    Izmailov, A. F., Solodov, M. V., and Uskov, E. (2012). Global convergence of augmented L agrangian methods applied to optimization problems with degenerate constraints, including problems with complementarity constraints. SIAM Journal on Optimization , 22(4):1579--1606

    2012

  24. [32]

    Kolstad, C. D. and Lasdon, L. S. (1990). Derivative evaluation and computational experience with large bilevel mathematical programs. Journal of Optimization Theory and Applications , 65:485--499

    1990

  25. [33]

    Labb \'e , M., Marcotte, P., and Savard, G. (1998). A bilevel model of taxation and its application to optimal highway pricing. Management Science , 44(12-part-1):1608--1622

    1998

  26. [34]

    and Hearn, D

    Lawphongpanich, S. and Hearn, D. W. (2004). An MPEC approach to second-best toll pricing. Mathematical Programming , 101(1):33--55

    2004

  27. [35]

    Li, J., Yu, J., Liu, B., Nie, Y., and Wang, Z. (2023). Achieving hierarchy-free approximation for bilevel programs with equilibrium constraints. In Proceedings of the 40th International Conference on Machine Learning , pages 20312--20335. PMLR

    2023

  28. [36]

    Li, J., Yu, J., Wang, Q., Liu, B., Wang, Z., and Nie, Y. M. (2022). Differentiable bilevel programming for S tackelberg congestion games. arXiv preprint arXiv:2209.07618

    2022 arXiv

  29. [37]

    Lim, A. C. (2002). Transportation network design problems: An MPEC approach . PhD thesis, Johns Hopkins University

    2002

  30. [38]

    Lin, G.-H., Xu, M., and Ye, J. J. (2014). On solving simple bilevel programs with a nonconvex lower level program. Mathematical Programming , 144(1):277--305

    2014

  31. [39]

    Lindsey, R. (2006). Do economists reach a conclusion on road pricing? Econ Journal Watch , 3(2):292--379

    2006

  32. [40]

    Liu, B., Ye, M., Wright, S., Stone, P., and Liu, Q. (2022). Bome! bilevel optimization made easy: A simple first-order approach. Advances in Neural Information Processing Systems , 35:17248--17262

    2022

  33. [41]

    Liu, R., Gao, J., Zhang, J., Meng, D., and Lin, Z. (2021). Investigating bi-level optimization for learning and vision from a unified perspective: A survey and beyond. IEEE Transactions on Pattern Analysis and Machine Intelligence , 44(12):10045--10067

    2021

  34. [42]

    Meng, Q., Yang, H., and Bell, M. G. (2001). An equivalent continuously differentiable model and a locally convergent algorithm for the continuous network design problem. Transportation Research Part B: Methodological , 35(1):83--105

    2001

  35. [43]

    Migdalas, A. (1995). Bilevel programming in traffic planning: Models, methods and challenge. Journal of Global Optimization , 7(4):381--405

    1995

  36. [44]

    Nie, Y. (2006). A programmer's manual for toolkit of network modeling. University of California, Davis, CA

    2006

  37. [45]

    and Wright, S

    Nocedal, J. and Wright, S. J. (1999). Numerical optimization . Springer

    1999

  38. [46]

    Outrata, J. V. (1990). On the numerical solution of a class of S tackelberg problems. Mathematical Methods of Operations Research , 34:255--277

    1990

  39. [47]

    and Rockafellar, R

    Patriksson, M. and Rockafellar, R. T. (2002). A mathematical model and descent algorithm for bilevel traffic management. Transportation Science , 36(3):271--291

    2002

  40. [48]

    Pigou, A. C. (1920). The economics of welfare . Palgrave Macmillan

    1920

  41. [49]

    Rockafellar, R. T. and Wets, R. J.-B. (2009). Variational analysis , volume 317. Springer Science & Business Media

    2009

  42. [50]

    and Gauvin, J

    Savard, G. and Gauvin, J. (1994). The steepest descent direction for the nonlinear bilevel programming problem. Operations Research Letters , 15(5):265--272

    1994

  43. [51]

    Sheffi, Y. (1985). Urban transportation networks , volume 6. Prentice-Hall, Englewood Cliffs, NJ

    1985

  44. [52]

    and Sumalee, A

    Shepherd, S. and Sumalee, A. (2004). A genetic algorithm based approach to optimal toll level and location problems. Networks and Spatial Economics , 4(2):161--179

    2004

  45. [53]

    Congestion pricing in N ew Y ork gets the go-ahead after all

    The Economist (2024). Congestion pricing in N ew Y ork gets the go-ahead after all. M aybe. https://www.economist.com/united-states/2024/11/21/congestion-pricing-in-new-york-gets-the-go-ahead-after-all-maybe. accessed: November 21, 2024

    2024

  46. [54]

    Transportation networks for research

    Transportation Networks for Research Core Team (2022). Transportation networks for research. Accessed October 1, 2024

    2022

  47. [55]

    Treiman, J. S. (1999). Lagrange multipliers for nonconvex generalized gradients with equality, inequality, and set constraints. SIAM Journal on Control and Optimization , 37(5):1313--1329

    1999

  48. [56]

    and Ghannadan, S

    Tuy, H. and Ghannadan, S. (1998). A new branch and bound method for bilevel linear programs. In Migdalas, A., Pardalos, P. M., and V \"a rbrand, P., editors, Multilevel optimization: Algorithms and applications , pages 231--249. Springer

    1998

  49. [57]

    Verhoef, E. T. (2002). Second-best congestion pricing in general networks. H euristic algorithms for finding second-best optimal toll levels and toll points. Transportation Research Part B: Methodological , 36(8):707--729

    2002

  50. [58]

    Vicente, L. N. and Calamai, P. H. (1994). Bilevel and multilevel programming: A bibliography review. Journal of Global Optimization , 5(3):291--306

    1994

  51. [59]

    Vickrey, W. S. (1969). Congestion theory and transport investment. The American Economic Review , 59(2):251--260

    1969

  52. [60]

    Von Stackelberg, H. (1934). Marktform und gleichgewicht . Springer

    1934

  53. [61]

    Wardrop, J. G. (1952). Some theoretical aspects of road traffic research. Proceedings of the Institution of Civil Engineers , 1(3):325--362

    1952

  54. [62]

    Xie, J., Nie, Y., and Liu, X. (2018). A greedy path-based algorithm for traffic assignment. Transportation Research Record , 2672(48):36--44

    2018

  55. [63]

    and Xie, C

    Xie, J. and Xie, C. (2016). New insights and improvements of using paired alternative segments for traffic assignment. Transportation Research Part B: Methodological , 93:406--424

    2016

  56. [64]

    and Lam, W

    Yan, H. and Lam, W. H. (1996). Optimal road tolls under conditions of queueing and congestion. Transportation Research Part A: Policy and Practice , 30(5):319--332

    1996

  57. [65]

    and Bell, M

    Yang, H. and Bell, M. G. (1997). Traffic restraint, road pricing and network equilibrium. Transportation Research Part B: Methodological , 31(4):303--314

    1997

  58. [66]

    and Huang, H.-J

    Yang, H. and Huang, H.-J. (2005). Mathematical and economic theory of road pricing . Emerald Group Publishing Limited

    2005

  59. [67]

    and Zhang, X

    Yang, H. and Zhang, X. (2003). Optimal toll design in second-best link-based congestion pricing. Transportation Research Record , 1857(1):85--92

    2003

  60. [68]

    Ye, J. J. and Zhu, D. (1995). Optimality conditions for bilevel programming problems. Optimization , 33(1):9--27

    1995

  61. [69]

    Yin, Y. (2000). Genetic-algorithms-based approach for bilevel programming models. Journal of Transportation Engineering , 126(2):115--120

    2000

  62. [70]

    Zheng, X., Sun, X., and Li, D. (2014). Improving the performance of MIQP solvers for quadratic programs with cardinality and minimum threshold constraints: A semidefinite program approach. INFORMS Journal on Computing , 26(4):690--703

    2014

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.