Assortment Optimization Under the Mallows model
We consider the assortment optimization problem when customer preferences follow a mixture of Mallows distributions. The assortment optimization problem focuses on determining the revenue/profit maximizing subset of products from a large universe of products; it is an important decision that is commonly faced by retailers in determining what to offer their customers. There are two key challenges: (a) the Mallows distribution lacks a closed-form expression (and requires summing an exponential number of terms) to compute the choice probability and, hence, the expected revenue/profit per customer; and (b) finding the best subset may require an exhaustive search. Our key contributions are an efficiently computable closed-form expression for the choice probability under the Mallows model and a compact mixed integer linear program (MIP) formulation for the assortment problem.
This paper studies an assortment optimization problem under the Mallow distribution model. It first offers a closed form expression for computing the choice probability of an item among a certain assortment that relies on discrete convolution. The authors argue that this result implies that the probability can be obtained efficiently using a Fourier transform method. On the other hand, they reject this closed form expression in their attempt to solve the assortment optimization where they rely on a recursive computation method to formulate a mixed integer linear programming problem formulation. With this formulation, they show that they have the capacity of solving problems with 20 items.
In my opinion, the authors do not provide convincing enough arguments that computing choice probabilities is as hard as they let it appear. The main reference that is stated relates to the difficulty of « computing the probability of a general parital order » which is not what is achieved by the methods that are proposed here. Instead, based on the repeated insertion procedure that is described in this paper (and obtained from Doignon et al. 2004) it appears that this probability can be efficiently computed using Monte-Carlo simulations (in fact, such simulations could even be used to construct a sample average approximation of problem (2)). I agree with the authors that the two methods that they propose are more efficient but have difficulty estimating the size of the contribution based on the text. Perhaps some information about sample average statistical convergence or some numerical evaluation of the methods would provide such an argument.  Regarding the second contribution, while I found the derivation of the MILP cleverly done. It fells short of convincing the reader that the model as real practical appeal. Indeed, in practice one would suspect that assortment planning have to handle numbers of items that are 10 to 100 times bigger than what the authors were able to achieve. One would also suspect that solutions to the assortment problem must be made almost instantaneously as users are visiting a web site and information are gathered about them.  Overall, I felt that there is a disconnect between section 3 and the rest of the paper that distracts the message that is made. Moreover, I believe that the MILP formulation has value but further efforts should be deployed in order to improve numerical performances if the goal is to have a practical impact with it. I would also encourage the author to identify a journal or conference that is more strongly oriented towards operations research or operations management.  Finally, here are some minor things that could be corrected : - Page 2, line 65 : « to to efficiently » should be « to efficiently » - Page 4, line 161 : « choosing a_k \in a_{i_l,j_l} » you should also define « l » here - Page 6, line 211 : « at position s » should sat « and at position s » - Page 7, line 228 : I don’t see how you can assume that a_1 \in S here given that a_1 is the preferred item in U. Please explain how the algorithm needs to change when it is not the case. Do we simply discard all items from U that are preferred to all items in S. - Page 8, line 280 : By « add cutting planes », I assume you mean « add valid inequalities » so that the LP relaxation is tighter. Or do you propose employing a decomposition scheme : e.g. master problem only holds the x_i’s while the slave problem takes care of the z’s and y’s