UCLA

The growing availability of data and recent developments in optimization methods and machine learning have led to a revolution in modern business analytics. In this Ph.D. dissertation, we propose two frameworks based on mixed-integer optimization that advance business analytics in the context of two important problems: product design with market share maximization and learning optimal decision trees.

In the first problem, we aim to find a product, as defined by its attributes, that maximizes market share, which is a weighted sum of logistic probabilities when we assume each customer segment follows a logit choice model to make a purchase. At first glance, this problem appears hopeless: one must optimize an objective function that is neither convex nor concave over an exponentially-sized discrete set of attribute combinations. Surprisingly, we show that this problem can be reformulated as a mixed-integer convex program by exploiting an economic model. We further propose an exact methodology for solving this problem based on modern integer, convex, and conic optimization techniques. Using synthetic problem instances and instances derived from real conjoint data sets, we show that our methodology can solve large problem instances to provable optimality or near-optimality within operationally feasible time frames.

In the second problem, we propose a mixed-integer program that learns optimal decision trees from data. While decision trees are among the most widely-used machine learning methods, their learning algorithms are usually based on top-down heuristics and cannot incorporate side constraints arising from real-world business operations. We show that our proposed mixed-integer formulation is theoretically stronger than other formulations in the literature by exploring its relaxation properties. We also develop a large-scale solution method based on constraint generation. Based on computational studies on real-world data sets, we show that our proposed model is significantly more tractable than alternative mixed-integer optimization models and our large-scale method based on constraint generation can further improve the solution time in several data sets.

Overall, we contribute to business analytics by proposing exact solution methods based on optimization to two significant but computationally challenging problems and developing efficient algorithms that make them more practical to use.