The widespread use of discrete choice models (DCMs) to capture preference heterogeneity introduces new challenges in optimization problems where demand, supply, or estimation objectives depend on individual choices. When advanced DCMs like mixed logit are used, simulation becomes necessary, adding considerable computational burden. This tractability often becomes the main bottleneck, limiting both model realism and the size of solvable problems. This thesis develops new algorithmic strategies to improve tractability in choice-based optimization relying on simulation-based DCMs. By exploiting structural properties of these modelsâ such as decision breakpoints and linear utilities under fixed simulation drawsâ we propose exact and heuristic methods that scale efficiently with alternatives, individuals, and draws. These contributions aim to bridge the gap between the expressiveness of modern DCMs and the computational effort required to solve large-scale choice-based optimization problems.
First, we introduce spatial Branch and Bound (B&B) and Branch and Benders Decomposition (B&BD) algorithms for the uncapacitated choice-based pricing problem (CPP). By reformulating the model from a mixed-integer linear program (MILP) to a quadratically constrained quadratic program with linear objective, we exploit McCormick relaxations and Benders decomposition to solve it more efficiently. We also develop the Breakpoint Exact Algorithm (BEA), which leverages utility breakpointsâ exact parameter values where one alternative becomes more attractive than anotherâ to scale computation polynomially in customer and draw counts. Our methods significantly outperform state-of-the-art solvers on pricing problems with mixed logit models, especially in low dimensions, and apply broadly to settings with linear-in-price utilities.
Next, we build on the developed methodology by addressing high-dimensional CPP instances and incorporating capacity constraints. To this end, we propose the Breakpoint Heuristic Algorithm (BHA), extend the BEA and BHA using an exogenous priority queue, and introduce valid inequalities for the exact B&B methods. Results show that the BEA outperforms MILP-based approaches under capacity constraints, and that the BHA performs remarkably well across both low- and high-dimensional settings, solving large instances quickly. In uncapacitated cases, the BHA and its iterated local search-based (ILS) extension solve large benchmark problems that are intractable for exact methods, while remaining near-optimal. Moreover, BHA solutions help improve B&B performance by guiding the search and tightening relaxations.
Finally, we apply the BHA framework to maximum simulated likelihood estimation (MSLE) of DCMs. We focus on latent class models, which are notoriously hard to estimate due to many local optima. We first reformulate MSLE as an MILP and adapt the BHA into a dedicated heuristic for estimation, termed BHA for MSLE, or BHAMSLE. This approach again expl
