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

Sunil Chopra*, Hyunwoo Park, Sangho Shim

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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 languageEnglish (US)
Pages (from-to)1327-1344
Number of pages18
JournalINFORMS Journal on Computing
Volume34
Issue number3
DOIs
StatePublished - 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

Fingerprint

Dive into the research topics of 'Extended Graph Formulation for the Inequity Aversion Pricing Problem on Social Networks'. Together they form a unique fingerprint.

Cite this