Network flow problems with pricing decisions

This paper considers a class of network flow problems in which the demand levels of the nodes are determined through pricing decisions representing the revenue received per unit demand at the nodes. We must simultaneously determine the pricing decisions and the network flow decisions in order to maximize profits, i.e., the revenues received from the pricing decisions minus the cost of the network flow decisions. Specializations of this class of problems have numerous applications in supply chain management. We show that the class of problems with a single pricing decision throughout the network can be solved in polynomial time under both continuous pricing restrictions and integer pricing restrictions. For the class of problems with customer-specific pricing decisions, we provide conditions under which the problem can be solved in polynomial-time for continuous pricing restrictions and prove that the problem is NP-hard for integer pricing restrictions.