  Scalable real-time assortment optimization has become essential in e-commerce
operations due to the need for personalization and the availability of a large
variety of items. While this can be done when there are simplistic assortment
choices to be made, the optimization process becomes difficult when imposing
constraints on the collection of relevant assortments based on insights by
store-managers and historically well-performing assortments. We design fast and
flexible algorithms based on variations of binary search that find the
(approximately) optimal assortment in this difficult regime. In particular, we
revisit the problem of large-scale assortment optimization under the
multinomial logit choice model without any assumptions on the structure of the
feasible assortments. We speed up the comparison steps using advances in
similarity search in the field of information retrieval/machine learning. For
an arbitrary collection of assortments, our algorithms can find a solution in
time that is sub-linear in the number of assortments, and for the simpler case
of cardinality constraints - linear in the number of items (existing methods
are quadratic or worse). Empirical validations using a real world dataset (in
addition to experiments using semi-synthetic data based on the Billion Prices
dataset and several retail transaction datasets) show that our algorithms are
competitive even when the number of items is $\sim 10^5$ ($10\times$ larger
instances than previously studied).
