The combinatorial pricing problem (CPP) is a bilevel problem in which the leader maximizes their revenue by imposing tolls on certain items that they can control. Based on the tolls set by the leader, the follower selects a subset of items corresponding to an optimal solution of a combinatorial optimization problem. To accomplish the leader’s goal, the tolls need to be sufficiently low to discourage the follower from choosing the items offered by the competitors. In this paper, we derive a single-level reformulation for the CPP by rewriting the follower’s problem as a longest path problem using a dynamic programming model and then taking its dual and applying strong duality. We proceed to solve the reformulation in a dynamic fashion with a cutting plane method. We apply this methodology to two distinct dynamic programming models—namely, a novel formulation designated as the selection diagram and the well-known decision diagram. We also produce numerical results to evaluate their performances across three different specializations of the CPP and a closely related problem that is the knapsack interdiction problem. Our results showcase the potential of the two proposed reformulations over the natural value function approach, expanding the set of tools to solve combinatorial bilevel programs. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: Financial support from IVADO and Fonds de recherche du Québec [FRQ-IVADO Research Chair], and the Natural Sciences and Engineering Research Council of Canada [Grants 2019-04557 and 2024-04051] is gratefully acknowledged. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0686 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0686 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

We study the network pricing problem where the leader maximizes revenue by determining the optimal amounts of tolls to charge on a set of arcs, under the assumption that the followers will react rationally and choose the shortest paths to travel. Many distinct single-level reformulations of this bilevel optimization program have been proposed; however, their relationship has not been established. In this paper, we aim to build a connection between those reformulations and explore the combination of the path representation with various modeling options, allowing us to generate 12 different reformulations of the problem. Moreover, we propose a new path enumeration scheme, path-based preprocessing, and hybrid framework to further improve performance and robustness when solving the final model. We provide numerical results, comparing all the derived reformulations and confirming the efficiency of the novel dimensionality reduction procedures.