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.
Original language | English (US) |
---|---|
Pages (from-to) | 1327-1344 |
Number of pages | 18 |
Journal | INFORMS Journal on Computing |
Volume | 34 |
Issue number | 3 |
DOIs | |
State | Published - May 2022 |
Funding
History: Accepted by David Alderson, Area Editor for Network Optimization: Algorithms & Applications. Funding: This work was supported by the New Faculty Startup Fund from Seoul National University.
Keywords
- business analytics
- graph theory
- inequity aversion pricing
- integer linear programming
- optimization
- revenue management
- social network
ASJC Scopus subject areas
- Software
- Information Systems
- Computer Science Applications
- Management Science and Operations Research