A Randomized Concave Programming Method for Choice Network Revenue Management

Abstract

Models incorporating more realistic models of customer behavior, as customers choosing from\nan offer set, have recently become popular in assortment optimization and revenue management.\nThe dynamic program for these models is intractable and approximated by a deterministic\nlinear program called the CDLP which has an exponential number of columns. However, when\nthe segment consideration sets overlap, the CDLP is difficult to solve. Column generation\nhas been proposed but finding an entering column has been shown to be NP-hard. In this\npaper we propose a new approach called SDCP to solving CDLP based on segments and their\nconsideration sets. SDCP is a relaxation of CDLP and hence forms a looser upper bound on\nthe dynamic program but coincides with CDLP for the case of non-overlapping segments. If\nthe number of elements in a consideration set for a segment is not very large (SDCP) can be\napplied to any discrete-choice model of consumer behavior. We tighten the SDCP bound by\n(i) simulations, called the randomized concave programming (RCP) method, and (ii) by adding\ncuts to a recent compact formulation of the problem for a latent multinomial-choice model of\ndemand (SBLP+). This latter approach turns out to be very effective, essentially obtaining\nCDLP value, and excellent revenue performance in simulations, even for overlapping segments.\nBy formulating the problem as a separation problem, we give insight into why CDLP is easy\nfor the MNL with non-overlapping considerations sets and why generalizations of MNL pose\ndifficulties. We perform numerical simulations to determine the revenue performance of all the\nmethods on reference data sets in the literature.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 28 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.