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

A Lagrangian decomposition scheme for the choice-based optimization framework

Speaker: Pacheco Meritxell

OR seminar, Erasmus University Rotterdam

June 26, 2020

A mismatch between supply and demand is the imbalance between the amount of supplies of a product or service with the corresponding willingness or need in the market. It affects a great deal of contexts and results in multiple consequences, which include reduced profitability, a decrease in consumer confidence and spillover effects. It is therefore important to allow for an appropriate demand representation and to explicitly consider the interplay between the individuals (demand) and the design and planning decisions to be made by the operator (supply). We propose a framework that enables the inclusion of discrete choice models (DCM), the most advanced and operational behavioral models at the disaggregate level, into mixed-integer linear problems (MILP). By relying on simulation, the behavioral preference structure of individuals is written as a set of mixed-integer linear constraints that can be embedded in any MILP formulation. For the interaction between the demand and the supply-related decisions to be captured, the only requirement is that such decisions are also explanatory variables of the DCM and appear linearly in the corresponding 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 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 (by running only 10% of the computational time used by the exact method).

[Download PDF]