Continuous pricing in a capacitated network under mixed multinomial logit demand

In this paper, we consider the deterministic multi-product multi-resource dynamic pricing (DMMDP) problem with continuous prices under the mixed multinomial logit (MMNL) choice model. The DMMDP problem arises in many applications where pricing decisions for multiple products should be optimized jointly, in particular when products have cross-effects on demands of other products and/or different products share the same resources (Talluri and van Ryzin 2004, Chen and Chen 2015). Applications are manifold, such as revenue management for airlines, railways, and hotels, assortment pricing in retailing, or product line pricing in consumer goods industries. The corresponding problem instances in practice are typically of large-scale size such that efficient solution techniques are required. The MMNL model is considered to be a powerful choice model that captures heterogeneous cross-effects in demand and that can approximate any random utility choice model arbitrarily closely (McFadden and Train 2000). It has received increasing attention in the related field of product assortment (PA) optimization, involving a seller’s discrete decisions about the selection of products and their prices (see, e.g., Feldman and Topaloglu 2015, Kunnumkal 2015, Méndez-Díaz 2015). Since the PA problem is NP-hard under the MMNL choice model (Rusmevichientong et al. 2014, Désir et al. 2014), much work has been focused on deriving upper bounds and efficient approximations, with the recent exception of Sen et al. (2017) who propose an exact conic MIP approach. On the other hand, the MMNL model and its incorporation into the DMMDP problem has only received scant attention in the dynamic pricing literature (e.g., Keller et al. 2014), despite its theoretical and practical relevance. The more common approach so far has been to incorporate the standard single-segment MNL choice model into the DMMDP problem (see, e.g., Dong et al. 2009, Zhang and Lu 2013, Keller et al. 2014). The logit profit function is known to be concave with respect to demand (Hanson and Martin 1996, Song and Xue 2007, Dong et al. 2009, Li and Huh 2011). In case of a single customer segment, there is a linearizable one-to-one mapping between product prices and MNL choice probabilities such that the demand model satisfies some regularity conditions, and the resulting optimization problem DMMDP is a convex optimization (minimization) problem in demand. In case the logit choice model encompasses multiple customer segments with heterogeneous price sensitivity parameters, the convex problem structure can still be maintained if it is feasible to simultaneously quote individual prices for the same product to each segment according to a first- or third-degree price discrimination (Schön 2010a, b). However, this requires the capability to identify à priori which customer segment an incoming sales request belongs to. In the more common case considered here, where the same product is offered at a uniform price to all customer requests occurring at the same time, the convexity property is lost, since non- convex constraints need to be introduced to ensure price consistency across segments with overlapping consideration sets. Accordingly, the DMMDP problem under MMNL choice is non-linear non-convex and thus difficult to solve in general. How to efficiently solve the continuous pricing problem with multiple segments to optimality is still an open problem, and we want to contribute to narrow this gap. Our contributions are as follows: • First, we analyze the DMMDP problem with continuous prices and price consistency constraints under the MMNL choice model in detail with regard to its mathematical structure. • We present an approximate optimization problem to derive an upper bound on the optimal profit and to determine heuristic solutions. The approximate problem is convex, and can therefore be solved efficiently even for large problem instances. An experimental study shows that the approach is very promising with regard to run time performance and solution quality. • We present a convex mixed-integer programming approach that allows to tighten the upper bound arbitrarily close-to-optimum and to determine provably near-optimal solutions of the original problem; to our knowledge, this is the first approach to approximately tackle the problem under the MMNL choice model with a performance guarantee; in our experiments, we are able to approximately solve medium-sized problem instances in reasonable time. Furthermore, we discuss the potential benefits we gain by allowing prices to be continuous rather than restricting them to discrete values with regard to solution quality and run time performance. • The suggested dynamic pricing approach is applied to a real-world revenue management case study of the German long-distance railway network