Extended Graph Formulation for the Inequity Aversion Pricing Problem on Social Networks
针对社交网络中考虑不公平厌恶的定价问题，提出一种扩展图模型，其线性规划松弛非常强，在无环网络上可得到整数解，并通过添加零半割显著缩小积分性差距。
The inequity aversion pricing problem aims to maximize revenue while providing prices to people connected in a social network such that connected people receive prices that are not too different. This problem is known to be NP-hard even when the number of prices offered is three. This paper provides an extended graph formulation for the problem whose LP-relaxation is shown to be very strong. We show that the extended graph relaxation is integral on a network without any cycle. We develop extended cycle inequalities and show that the extended cycle inequalities cut off all the fractional extreme points of the extended graph relaxation on a cycle. We generalize cycle inequalities to zero half cuts performing a Chvátal–Gomory procedure on a cycle. Computational experiments show that the extended graph relaxation results in an integer solution for most problem instances with very small gaps (less than 3%) from optimality for the remaining instances. The addition of zero half cuts reduces the integrality gap significantly on the few difficult instances. Summary of Contribution: The inequity aversion pricing problem aims to maximize revenue while providing prices to people connected in a social network such that connected people receive prices that are not too different. This paper provides an extended graph formulation of this practical revenue management problem whose LP-relaxation is shown to be very strong. The authors show that the extended graph relaxation is integral on a network without any cycle. They develop extended cycle inequalities and generalize them to zero-half cuts. Computational experiments show that the extended graph formulation results in an integer solution or a very small integrality gap. For difficult instances, the addition of zero half cuts significantly reduces the integrality gap.