A general framework for the integration of complex choice models into mixed integer optimization

The objective of this thesis is to develop a general methodology to incorporate a disaggregate demand representation in supply-oriented optimization problems that allows to capture the interplay between the behavior of individuals and the decisions to be optimized. To this end, we propose a modeling framework for the integration of discrete choice models (DCM) in mixed-integer linear problems (MILP), and we show that it is both flexible and operational on realistic instances. In particular, we develop algorithms to enhance the tractability of the framework, and we illustrate its applicability with two relevant optimization problems that arise in a great deal of contexts. The demand functions generated from DCM are highly non-linear and non-convex, and are not always available in closed form. In this thesis, we avoid the use of such functions by specifying the preference structure of DCM directly in terms of the related structural equations (utility functions). We rely on simulation in order to handle the probabilistic nature of these equations by drawing from the distribution of the associated random component. This yields a mixed-integer linear set of constraints that can be embedded in any MILP formulation. The only requirement is that the decisions to be optimized that are also explanatory variables of the DCM, and therefore capture the interactions, appear linearly in the structural equations. The disaggregate nature of DCM, together with the associated simulation-based linearization, comes with a high computational complexity. Motivated by the decomposable structure of the framework along the two dimensions it is built on, the individuals and the simulation draws, we characterize a Lagrangian decomposition scheme that enables to solve larger instances, at least approximatively. Indeed, the performed tests show that near-optimal solutions are obtained in a much reduced computational time. The framework is sufficiently general to accommodate a wide variety of relevant optimization problems. The main strength is that the DCM does not need to be tailored to the formulation, i.e., it can be taken as such from the literature. In particular, it does not have to be a DCM that relies on simplistic assumptions, such as the logit model, and more advanced DCM such as mixtures of logit models can be integrated. In this thesis, we consider and solve two problems in order to illustrate the versatility of the framework, namely operator-centric profit maximization and traveler-centric design of a transportation system. The former assumes an operator that offers services to a market with the aim of maximizing its profit. The latter formulates the pricing and design of a transportation system such that a measure of welfare is maximized. The key quantitative element of welfare analysis in the context of DCM, the expected maximum utility, is readily available in the framework. This represents a significant advantage because it allows not to deal with the complex non-linear formulations of this quantity as provided by discrete choice theory. In summary, this thesis makes relevant contributions on the integration of DCM in MILP, and shows their applicability by relying on real-world optimization problems. The proposed models and algorithms shed some light on the benefits of incorporating individual behavior in operational decisions for any industry with close interactions between the demand and the supply.