Pacheco, M., Sharif Azadeh, S., Bierlaire, M., and Gendron, B.

A Lagrangian relaxation method for a choice-based optimization framework capturing the demand-supply interaction

Speaker: Pacheco Meritxell

Annual international conference of the German Operations Research Society (OR2017), Freie Universität Berlin

September 07, 2017

The integration of customer behavioral models in optimization provides a better understanding of the preferences of clients (the demand) to policy makers while planning for their systems (the supply). On the one hand, these preferences are formalized with discrete choice models, which are the state-of-the-art for the mathematical modeling of demand. On the other hand, the optimization models that are considered to design and configure a system are associated with (mixed) integer linear problems (MILP). The complexity of discrete choice models leads to mathematical formulations that are highly nonlinear and nonconvex in the variables of interest, and are therefore difficult to be included in MILP. In this research, we present a general framework that overcomes these limitations and is able to integrate advanced discrete choice models in MILP. Since the formulation has designed to be linear, the price to pay is its high dimension, which results in a computationally expensive problem. To address this issue, and given the underlying structure of the model, we propose a Lagrangian relaxation method by identifying two subproblems with common variables: one concerning the choices of customers and another concerning the design variables of the operator. A subgradient method is characterized in order to approximate the associated Lagrangian dual.