  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 2 distinct dynamic programming models, namely, a
novel formulation designated as selection diagram and the well-known decision
diagram. We also produce numerical results to evaluate their performances
across 3 different specializations of the CPP and a closely related problem
that is the knapsack interdiction problem. Our results showcase the potential
of the 2 proposed reformulations over the natural value function approach,
expanding the set of tools to solve combinatorial bilevel programs.
