  We study the assortment optimization problem under general linear
constraints, where the customer choice behavior is captured by the Cross-Nested
Logit model. In this problem, there is a set of products organized into
multiple subsets (or nests), where each product can belong to more than one
nest. The aim is to find an assortment to offer to customers so that the
expected revenue is maximized. We show that, under the Cross-Nested Logit
model, the assortment problem is NP-hard, even without any constraints. To
tackle the assortment optimization problem, we develop a new discretization
mechanism to approximate the problem by a linear fractional program with a
performance guarantee of $\frac{1 - \epsilon}{1+\epsilon}$, for any accuracy
level $\epsilon>0$. We then show that optimal solutions to the approximate
problem can be obtained by solving mixed-integer linear programs. We further
show that our discretization approach can also be applied to solve a joint
assortment optimization and pricing problem, as well as an assortment problem
under a mixture of Cross-Nested Logit models to account for multiple classes of
customers. Our empirical results on a large number of randomly generated test
instances demonstrate that, under a performance guarantee of 90%, the
percentage gaps between the objective values obtained from our approximation
methods and the optimal expected revenues are no larger than 1.2%.
