Solving Combinatorial Pricing Problems Using Embedded Dynamic Programming Models

References

• Bergman D, Cire AA, van Hoeve WJ, Hooker JN (2016) Discrete optimization with decision diagrams. INFORMS J. Comput. 28(1):47–66.Link, Google Scholar
• Bertsekas D (2012) Dynamic Programming and Optimal Control, vol. I, 4th ed. (Athena Scientific, Belmont, MA).Google Scholar
• Bouhtou M, van Hoesel S, van der Kraaij AF, Lutton JL (2007) Tariff optimization in networks. INFORMS J. Comput. 19(3):458–469.Link, Google Scholar
• Briest P, Hoefer M, Krysta P (2012a) Stackelberg network pricing games. Algorithmica 62(3–4):733–753.Crossref, Google Scholar
• Briest P, Gualà L, Hoefer M, Ventre C (2012b) On Stackelberg pricing with computationally bounded customers. Networks 60(1):31–44.Crossref, Google Scholar
• Brotcorne L, Labbé M, Marcotte P, Savard G (2000) A bilevel model and solution algorithm for a freight tariff-setting problem. Transportation Sci. 34(3):289–302.Link, Google Scholar
• Bui QM (2024) Methods for solving combinatorial pricing problems. PhD thesis, Université de Montréal, Montreal.Google Scholar
• Bui QM, Carvalho M, Neto J (2025) Solving combinatorial pricing problems using embedded dynamic programming models. http://dx.doi.org/10.1287/ijoc.2024.0686.cd, https://github.com/INFORMSJoC/2024.0686.Google Scholar
• Bui QM, Gendron B, Carvalho M (2022) A catalog of formulations for the network pricing problem. INFORMS J. Comput. 34(5):2658–2674.Link, Google Scholar
• Böhnlein T, Schaudt O, Schauer J (2023) Stackelberg packing games. Theoretical Comput. Sci. 943:16–35.Crossref, Google Scholar
• Caprara A, Carvalho M, Lodi A, Woeginger GJ (2016) Bilevel knapsack with interdiction constraints. INFORMS J. Comput. 28(2):319–333.Link, Google Scholar
• Cardinal J, Demaine ED, Fiorini S, Joret G, Langerman S, Newman I, Weimann O (2011) The Stackelberg minimum spanning tree game. Algorithmica 59:129–144.Crossref, Google Scholar
• Della Croce F, Scatamacchia R (2020) An exact approach for the bilevel knapsack problem with interdiction constraints and extensions. Math. Program. 183(1–2):249–281.Crossref, Google Scholar
• DeNegre S (2011) Interdiction and discrete bilevel linear programming. PhD thesis, Lehigh University, Bethlehem, PA.Google Scholar
• Didi-Biha M, Marcotte P, Savard G (2006) Path-based formulations of a bilevel toll setting problem. Dempe S, Kalashnikov V, eds. Optimization with Multivalued Mappings: Theory, Applications, and Algorithms (Springer US, Boston), 29–50.Crossref, Google Scholar
• Fischetti M, Monaci M, Sinnl M (2018) A dynamic reformulation heuristic for generalized interdiction problems. Eur. J. Oper. Res. 267(1):40–51.Crossref, Google Scholar
• Fischetti M, Ljubić I, Monaci M, Sinnl M (2017) A new general-purpose algorithm for mixed-integer bilevel linear programs. Oper. Res. 65(6):1615–1637.Link, Google Scholar
• Fischetti M, Ljubić I, Monaci M, Sinnl M (2019) Interdiction games and monotonicity, with application to knapsack problems. INFORMS J. Comput. 31(2):390–410.Link, Google Scholar
• Gurobi Optimization, LLC (2022) Gurobi Optimizer reference manual. Accessed April 22, 2025, https://docs.gurobi.com/projects/optimizer/en/current/index.html.Google Scholar
• Hansen N, Müller SD, Koumoutsakos P (2003) Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). Evol. Comput. 11(1):1–18.Crossref, Google Scholar
• Heilporn G, Labbé M, Marcotte P, Savard G (2006) New formulations and valid inequalities for the toll setting problem. IFAC Proc. Vol. 39(3):431–436.Crossref, Google Scholar
• Labbé M, Marcotte P, Savard G (1998) A bilevel model of taxation and its application to optimal highway pricing. Management Sci. 44(12-part-1):1608–1622.Link, Google Scholar
• Lozano L, Bergman D, Cire AA (2022) Constrained shortest-path reformulations for discrete bilevel and robust optimization. Preprint, submitted June 26, https//dx.doi.org/10.48550/arXiv.2206.12962.Google Scholar
• McCormick GP (1976) Computability of global solutions to factorable nonconvex programs: Part I—Convex underestimating problems. Math. Program. 10(1):147–175.Crossref, Google Scholar
• Pferschy U, Nicosia G, Pacifici A, Schauer J (2021) On the Stackelberg knapsack game. Eur. J. Oper. Res. 291(1):18–31.Crossref, Google Scholar
• Roch S, Savard G, Marcotte P (2005) An approximation algorithm for Stackelberg network pricing. Networks 46(1):57–67.Crossref, Google Scholar
• Tahernejad S, Ralphs TK, DeNegre ST (2020) A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation. Math. Program. Comput. 12(4):529–568.Crossref, Google Scholar
• Tang Y, Richard JPP, Smith JC (2016) A class of algorithms for mixed-integer bilevel min–max optimization. J. Glob. Optim. 66:225–262.Crossref, Google Scholar
• Weninger N, Fukasawa R (2023) A fast combinatorial algorithm for the bilevel knapsack problem with interdiction constraints. Del Pia A, Kaibel V, eds. Integer Programming and Combinatorial Optimization (Springer International Publishing, Cham, Switzerland), 438–452.Crossref, Google Scholar