Solving utility-maximization selection problems with Multinomial Logit demand: Is the First-Choice model a good approxim
- PDF / 377,639 Bytes
- 21 Pages / 439.37 x 666.142 pts Page_size
- 104 Downloads / 154 Views
Solving utility-maximization selection problems with Multinomial Logit demand: Is the First-Choice model a good approximation? Laurent Alfandari1 · Victoire Denoyel2
· Aurélie Thiele3
© Springer Science+Business Media, LLC, part of Springer Nature 2019
Abstract We investigate First-Choice (FC) assignment models, a simple type of choice model where customers are allocated to their highest utility option, as a heuristic or starting point for the Multinomial Logit (MNL) model in the context of selection problems with a utility maximization objective. This type of problem occurs in a variety of applications, from location problems to assortment planning or transportation planning. FC assignment models are less refined but computationally more tractable than the more commonly used MNL. MNL suffers from tractability issues due to its nonlinear structure when used within a large size optimization problem with binary decision variables. We design the first comparison of the two modeling frameworks in a context of customer utility maximization for selection problems with binary variables. We provide a probabilistic analysis of the expected customer choice probabilities, document the computational challenges faced by the MNL model in our setting and show in numerical experiments that the FC model exhibits excellent performance as an approximation of the MNL model with an average gap for instance of at most 2.2% for uniformly distributed utilities and of at most 1.4% for normally distributed utilities (and below 1% in a majority of test cases). The key contribution of this paper is to build the case for the FC model as a tractable, high-quality approximation of the MNL model for binary selection problems with utility maximization. Keywords Combinatorial optimization · Discrete choice modeling · Multinomial Logit · Integer linear programming · Approximation
B
Victoire Denoyel [email protected]
1
ESSEC Business School, Avenue Bernard Hirsch, Cergy-Pontoise, France
2
Mercy College, 66W 35th street, New York, NY 10001, USA
3
Southern Methodist University, Dallas, TX 75205, USA
123
Annals of Operations Research
1 Introduction 1.1 Motivation In selection problems with a utility maximization objective, a decision maker selects a subset of options (for example, products or sites) to offer to her consumers and maximize their overall satisfaction. Customers consider all offered options and make a choice, according to utility theory, that maximizes their individual utility. Researchers have developed different tools in Discrete Choice Modeling (DCM) to model this customer choice. The most commonly used choice model is the Multinomial Logit model, described in detail in Sect. 2. In this model, evi the probability for a customer of choosing option i in a set K is expressed as , vk k∈K e where the (vk ) are the utilities attributed to each option. When used to model the demand in the context of selection problems, the MNL model presents some notable computational challenges due to its nonlinear structure in the binary dec
Data Loading...
