EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

2806. Modern column generation for the estimation of non-parametric discrete-choice models

Invited abstract in session MD-59: Customer behaviour, stream Pricing and Revenue Management.

Monday, 14:30-16:00
Room: S08 (building: 101)

Authors (first author is the speaker)

1. Luciano Costa
Production Engineering Department, Federal University of Paraíba
2. Gerardo Berbeglia
Melbourne Business School
3. Claudio Contardo
Concordia University
4. Jean-François Cordeau
Department of Logistics and Operations Management, HEC Montréal

Abstract

Discrete choice models (DCMs) provide probabilities for individuals choosing a certain alternative when faced with a set of limited options. DCMs can be parametric or non-parametric. Parametric models are easier to estimate but require assumptions about individuals' preferences, while non-parametric models rely solely on training data without any assumptions. Ranked-list methods are popular non-parametric models and capture individuals’ behavior by associating them with preference lists of options sorted in decreasing order of preference. Individuals are assumed to always choose the option best placed in their preference list when confronted with an alternative. Despite the generality and simplicity of ranked-list methods, a major drawback associated with them is the exponential increase in the number of potential lists. Column generation (CG) can be employed to address this issue, with the CG subproblem being modeled as a generalized linear ordering problem (GLOP). In this work, we propose a dynamic programming algorithm to solve GLOPs. The proposed method is generic and capable of handling different settings without requiring drastic changes in its implementation. When incorporated into maximum likelihood and minimum L1 estimators, our algorithm efficiently generates preference lists. The algorithm performs well when facing instances with several observations, which is crucial as non-parametric choice models heavily rely on data volume for accurate estimations.

Keywords

Status: accepted

Back to the list of papers