论文标题
多商品网络定价问题的复杂性中的不对称性
Asymmetry in the Complexity of the Multi-Commodity Network Pricing Problem
论文作者
论文摘要
网络定价问题（NPP）是一个折磨问题，领导者通过决定图中某些弧的价格来优化其收入，同时期望追随者（也称为商品）根据这些价格选择最短的路径。在本文中，我们研究了NPP相对于两个参数的复杂性：收费弧的数量和商品数量。我们设计了一种简单的算法，表明如果固定了通行弧的数量，则可以在多项式时间内相对于商品数量解决该问题。相比之下，即使只有一种商品，一旦未固定收费弧的数量，问题就会变成NP-HARD。我们在复杂性中表征了这种不对称性，其新型属性被称为强二极管可行性。最后，我们描述了一种基于此属性对NPP产生有效不平等的算法，并以数值结果适应了其在用大量商品数量来解决NPP方面的有效性。
The network pricing problem (NPP) is a bilevel problem, where the leader optimizes its revenue by deciding on the prices of certain arcs in a graph, while expecting the followers (also known as the commodities) to choose a shortest path based on those prices. In this paper, we investigate the complexity of the NPP with respect to two parameters: the number of tolled arcs, and the number of commodities. We devise a simple algorithm showing that if the number of tolled arcs is fixed, then the problem can be solved in polynomial time with respect to the number of commodities. In contrast, even if there is only one commodity, once the number of tolled arcs is not fixed, the problem becomes NP-hard. We characterize this asymmetry in the complexity with a novel property named strong bilevel feasibility. Finally, we describe an algorithm to generate valid inequalities to the NPP based on this property, accommodated with numerical results to demonstrate its effectiveness in solving the NPP with a high number of commodities.
