Extended Graph Formulation for the Inequity Aversion Pricing Problem on Social Networks

Sunil Chopra (), Hyunwoo Park () and Sangho Shim ()
Additional contact information
Sunil Chopra: Kellogg School of Management, Northwestern University, Evanston, Illinois 60208
Hyunwoo Park: Graduate School of Data Science, Seoul National University, Seoul 08826, Republic of Korea
Sangho Shim: School of Engineering, Mathematics and Science, Robert Morris University, Moon Township, Pennsylvania 15108

INFORMS Journal on Computing, 2022, vol. 34, issue 3, 1327-1344

Abstract: 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.

Keywords: optimization; integer linear programming; graph theory; business analytics; revenue management; inequity aversion pricing; social network (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2021.1148 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:34:y:2022:i:3:p:1327-1344

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().