Jean-François Cordeau

Luciano Costa, Gerardo Berbeglia, Claudio Contardo et al.

This paper studies the estimation of ranked-list discrete choice models with single and multiple purchases. In this setting, each consumer type is characterized by a ranking over a subset of products and a desired number of purchases, and the estimation task is to identify the set of consumer types and their probabilities that best explain the observed transactional data. This problem is computationally challenging due to the exponential number of possible consumer types and becomes more difficult when multiple purchases are allowed. We propose a column generation framework for this problem. Our main contribution is a dynamic programming algorithm for the column generation subproblem. This subproblem generalizes the linear ordering problem and incorporates acceleration techniques to improve computational efficiency. To the best of our knowledge, this is the first dynamic programming-based approach for generating consumer types in non-parametric models. The proposed framework supports multiple model variants with minor modifications. Computational experiments on synthetic and real data show substantial speedups over existing methods while maintaining high solution quality, and demonstrate effectiveness in both estimation and assortment optimization.

Charly Robinson La Rocca, Emma Frejinger, Jean-François Cordeau

Current state-of-the-art solvers for mixed-integer programming (MIP) problems are designed to perform well on a wide range of problems. However, for many real-world use cases, problem instances come from a narrow distribution. This has motivated the development of specialized methods that can exploit the information in historical datasets to guide the design of heuristics. Recent works have shown that machine learning (ML) can be integrated with an MIP solver to inject domain knowledge and efficiently close the optimality gap. This hybridization is usually done with deep learning (DL), which requires a large dataset and extensive hyperparameter tuning to perform well. This paper proposes an online heuristic that uses the notion of entropy to efficiently build a model with minimal training data and tuning. We test our method on the locomotive assignment problem (LAP), a recurring real-world problem that is challenging to solve at scale. Experimental results show a speed up of an order of magnitude compared to a general purpose solver (CPLEX) with a relative gap of less than 2%. We also observe that for some instances our method can discover better solutions than CPLEX within the time limit.