pith. sign in

arxiv: 2605.06948 · v1 · submitted 2026-05-07 · 💻 cs.DS

Modern column generation for estimating single- and multi-purchase ranked list choice models

Luciano Costa , Gerardo Berbeglia , Claudio Contardo , Jean-Fran\c{c}ois Cordeau This is my paper

Pith reviewed 2026-05-11 01:05 UTC · model grok-4.3

classification 💻 cs.DS
keywords column generationdynamic programmingranked list choice modelsdiscrete choice estimationmulti-purchase modelsconsumer typesassortment optimization
0
0 comments X

The pith

Dynamic programming solves the column generation subproblem for estimating ranked list choice models with single and multi-purchases.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper develops a column generation approach to estimate non-parametric ranked list choice models from transaction data, where each consumer type is a ranking of products paired with a purchase quantity. The key innovation is a dynamic programming method to solve the subproblem of finding the most promising new consumer type to add to the model. This addresses the challenge of an exponentially large set of possible types, which grows even larger with multiple purchases allowed. If the method works, it provides a scalable way to fit detailed preference models without strong parametric assumptions, directly supporting better assortment decisions.

Core claim

The paper presents a dynamic programming algorithm that solves the pricing problem in a column generation framework for single- and multi-purchase ranked list choice models. This algorithm generalizes the linear ordering problem and uses acceleration techniques to generate consumer types efficiently, representing the first dynamic programming-based method for this task in non-parametric choice models.

What carries the argument

A dynamic programming algorithm that finds the consumer type with the highest reduced cost to add as a new column, generalizing the linear ordering problem with speed-up techniques.

Load-bearing premise

That an efficient dynamic programming procedure exists for exactly solving the column generation subproblem in both single- and multi-purchase cases without losing the convergence properties of the master problem.

What would settle it

Running the method on instances where the subproblem is known to be hard and observing that it either returns suboptimal columns or exceeds reasonable time limits without producing quality estimates.

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper develops a column generation framework to estimate ranked-list discrete choice models that allow both single and multiple purchases per consumer type. Each type is defined by a ranking over a product subset and a purchase quantity; the goal is to recover the support and probabilities that best fit observed transaction data. The central technical contribution is a dynamic programming algorithm for the pricing subproblem that generalizes the linear ordering problem and incorporates acceleration techniques. The same framework is shown to support assortment optimization with only minor changes. Experiments on synthetic and real instances are reported to yield substantial speedups relative to existing methods while preserving solution quality.

Significance. If the dynamic programming procedure solves the column-generation subproblem to exact optimality for both single- and multi-purchase variants, the approach supplies the first exact, non-parametric method that scales beyond the exponential consumer-type space while retaining the convergence guarantees of column generation. This is a meaningful algorithmic advance for choice-model estimation and downstream assortment problems, especially because the method is presented as self-contained against standard optimization benchmarks and does not rely on parameter fitting or self-referential reductions.

minor comments (3)
  1. [Abstract] Abstract: the statements 'substantial speedups' and 'high solution quality' are not accompanied by any numerical values, baseline comparisons, or error metrics. Adding at least one concrete performance figure (e.g., average runtime ratio or MAPE) would make the empirical claim immediately verifiable.
  2. [Computational experiments] The experimental section should report the number of synthetic and real instances, the precise baselines used, whether error bars or statistical tests accompany the speed-up claims, and the precise definition of 'solution quality' (e.g., log-likelihood gap or out-of-sample prediction error).
  3. [Dynamic programming algorithm] Notation for the multi-purchase extension (ranking plus purchase quantity) should be introduced once and used consistently; a small table summarizing the differences between the single- and multi-purchase DP recurrences would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary and recommendation for minor revision. The report correctly identifies the dynamic programming algorithm for the column-generation pricing subproblem as the key technical contribution, along with its generalization of the linear ordering problem, support for both single- and multi-purchase variants, and applicability to assortment optimization. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper's central contribution is a dynamic programming algorithm for the column-generation pricing subproblem that generalizes the linear ordering problem for both single- and multi-purchase ranked-list choice models. This algorithmic result is presented as self-contained, with explicit claims of being the first DP-based approach for generating consumer types in non-parametric models. No load-bearing step reduces by construction to fitted inputs, self-citations, or renamed known results; the derivation relies on standard optimization techniques and is validated against external benchmarks via computational experiments. The overall estimation procedure preserves optimality guarantees through exact subproblem solution without internal reduction to the target quantities.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the standard domain assumption that observed transactions arise from a mixture of ranked-list consumer types with purchase quantities; no free parameters or new entities are introduced beyond this modeling framework.

axioms (1)
  • domain assumption Consumer behavior can be represented as a probability distribution over ranked lists of products with associated desired purchase quantities.
    This is the foundational modeling assumption stated in the problem setting that enables the estimation task.

pith-pipeline@v0.9.0 · 5482 in / 1266 out tokens · 51751 ms · 2026-05-11T01:05:37.064611+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

76 extracted references · 76 canonical work pages

  1. [1]

    He, Taotao and Wu, Zhongqi and Zhang, Yating , journal =. On. 2026 , doi =

    work page 2026

  2. [2]

    Manufacturing & Service Operations Management , volume =

    Bodea, Tudor and Ferguson, Mark and Garrow, Laurie , title =. Manufacturing & Service Operations Management , volume =

    work page

  3. [3]

    Operations Research , volume =

    Golrezaei, Negin and Manshadi, Vahideh and Schneider, Jon and Sekar, Shreyas , title =. Operations Research , volume =

    work page

  4. [4]

    Operations Research , volume=

    The approximability of assortment optimization under ranking preferences , author=. Operations Research , volume=. 2018 , publisher=

    work page 2018

  5. [5]

    Management Science , year=

    Representing random utility choice models with neural networks , author=. Management Science , year=

    work page

  6. [6]

    Revenue management and pricing analytics , pages=

    Assortment optimization , author=. Revenue management and pricing analytics , pages=. 2019 , publisher=

    work page 2019

  7. [7]

    Mallows-Smoothed Distribution over Rankings Approach for Modeling Choice , journal =

    D. Mallows-Smoothed Distribution over Rankings Approach for Modeling Choice , journal =

    work page

  8. [8]

    Available at SSRN 4539900 , year=

    A mallows-type model for preference learning from (ranked) choices , author=. Available at SSRN 4539900 , year=

    work page

  9. [9]

    Operations Research , volume=

    Personalized retail promotions through a directed acyclic graph--based representation of customer preferences , author=. Operations Research , volume=. 2022 , publisher=

    work page 2022

  10. [10]

    Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , pages =

    Kamishima, Toshihiro , title =. Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , pages =. 2003 , isbn =

    work page 2003

  11. [11]

    European Journal of Operational Research , volume=

    Efficient elementary and restricted non-elementary route pricing , author=. European Journal of Operational Research , volume=. 2014 , publisher=

    work page 2014

  12. [12]

    Mathematical Programming , Year =

    An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts , Author =. Mathematical Programming , Year =

    work page

  13. [13]

    Production and Operations Management , volume =

    Rusmevichientong, Paat and Shmoys, David and Tong, Chaoxu and Topaloglu, Huseyin , title =. Production and Operations Management , volume =

    work page

  14. [14]

    Psychological Review , volume=

    A law of comparative judgment , author=. Psychological Review , volume=. 1927 , publisher=

    work page 1927

  15. [15]

    International Journal of Production Economics , year =

    Mengmeng Wang and Xun Zhang and Xiaolong Li , title =. International Journal of Production Economics , year =

    work page

  16. [16]

    arXiv preprint arXiv:1908.01109 , year=

    The use of binary choice forests to model and estimate discrete choices , author=. arXiv preprint arXiv:1908.01109 , year=

    work page arXiv 1908

  17. [17]

    Management Science , volume=

    Decision forest: A nonparametric approach to modeling irrational choice , author=. Management Science , volume=. 2022 , publisher=

    work page 2022

  18. [18]

    Networks , volume =

    Feillet, Dominique and Dejax, Pierre and Gendreau, Michel and Gueguen, Cyrille , title =. Networks , volume =

    work page

  19. [19]

    Electronic Notes in Theoretical Computer Science , title =

    Bal\'azs Dezs. Electronic Notes in Theoretical Computer Science , title =. 2011 , issn =

    work page 2011

  20. [20]

    Networks: An International Journal , volume=

    New dynamic programming algorithms for the resource constrained elementary shortest path problem , author=. Networks: An International Journal , volume=. 2008 , publisher=

    work page 2008

  21. [21]

    Data-driven Assortment Optimization , institution =

    Bertsimas, Dimitris and Mi. Data-driven Assortment Optimization , institution =. 2016 , address =

    work page 2016

  22. [22]

    Jena, Sanjay Dominik and Lodi, Andrea and Sole, Claudio , journal =

    work page

  23. [23]

    Operations Research , number =

    Ho-Nguyen, Nam and K. Operations Research , number =

    work page

  24. [24]

    Chen, Ningyuan and Hu, Ming , journal =

    work page

  25. [25]

    Heger, Julia and Klein, Robert , journal =

    work page

  26. [26]

    Hadi and Malekhosseini, Razieh and Bagherifard, Karamollah , journal =

    Moula, Hamed Sherafat and Yaghoubyan, S. Hadi and Malekhosseini, Razieh and Bagherifard, Karamollah , journal =

    work page

  27. [27]

    Yu, Yugang and Wang, Bo and Zheng, Shengming , journal =

    work page

  28. [28]

    Operations Research , number =

    K. Operations Research , number =

    work page

  29. [29]

    Costa, Luciano and Contardo, Claudio and Desaulniers, Guy , journal =

    work page

  30. [30]

    A discrete choice model based on random utilities for exit choice in emergency evacuations , year =

    Ruggiero Lovreglio and Dino Borri and Luigi dell’Olio and Angel Ibeas , journal =. A discrete choice model based on random utilities for exit choice in emergency evacuations , year =

    work page

  31. [31]

    Cirillo, Cinzia and Xu, Renting , journal =

    work page

  32. [32]

    INFORMS Journal on Computing , year =

    Luciano Costa and Claudio Contardo and Guy Desaulniers and Julian Yarkony , title =. INFORMS Journal on Computing , year =

    work page

  33. [33]

    Management Science , title =

    Berbeglia, Gerardo and Garassino, Agust\'. Management Science , title =. 2022 , number =

    work page 2022

  34. [34]

    Block and Jacob Marschak , title =

    H.D. Block and Jacob Marschak , title =. 1959 , type =

    work page 1959

  35. [35]

    1965 , author =

    Individual Choice Behavior , publisher =. 1965 , author =

    work page 1965

  36. [36]

    , title =

    Bhat, Chandra R. , title =. Transportation Science , year =

    work page

  37. [37]

    Journal of Applied Econometrics , year =

    McFadden, Daniel and Train, Kenneth , title =. Journal of Applied Econometrics , year =

    work page

  38. [38]

    2009 , author =

    Discrete Choice Methods with Simulation , publisher =. 2009 , author =

    work page 2009

  39. [39]

    2019 , author =

    Revenue Management and Pricing Analytics , publisher =. 2019 , author =

    work page 2019

  40. [40]

    Management Science , year =

    Talluri, Kalyan and. Management Science , year =

    work page

  41. [41]

    Algorithmica , year =

    Berbeglia, Gerardo and Joret, Gwena. Algorithmica , year =

    work page

  42. [42]

    Operations Research , year =

    Vulcano, Gustavo and. Operations Research , year =

    work page

  43. [43]

    Manufacturing & Service Operations Management , year =

    Misic, Velibor and Perakis, Georgia , title =. Manufacturing & Service Operations Management , year =

    work page

  44. [44]

    Operations Research , year =

    Bertsimas, Dimitris and Mi. Operations Research , year =

    work page

  45. [45]

    Dempster, A. P. and Laird, N. M. and Rubin, D. B. , journal =. Maximum Likelihood from Incomplete Data Via the EM Algorithm , year =

    work page

  46. [46]

    Strauss and Robert Klein and Claudius Steinhardt , title =

    Arne K. Strauss and Robert Klein and Claudius Steinhardt , title =. European Journal of Operational Research , year =

    work page

  47. [47]

    Retail Supply Chain Management: Quantitative Models and Empirical Studies , publisher =

    K. Retail Supply Chain Management: Quantitative Models and Empirical Studies , publisher =. 2015 , editor =

    work page 2015

  48. [48]

    INFORMS Journal on Optimization , volume =

    Jena, Sanjay Dominik and Lodi, Andrea and Palmer, Hugo and Sole, Claudio , title =. INFORMS Journal on Optimization , volume =

    work page

  49. [49]

    Discrete Applied Mathematics , year =

    M. Discrete Applied Mathematics , year =

    work page

  50. [50]

    Management Science , year =

    work page

  51. [51]

    2018 , url =

    Berbeglia, Gerardo and Garassino, Agusttn and Vulcano, Gustavo , title =. 2018 , url =

    work page 2018

  52. [52]

    Management Science , year =

    Jagabathula, Srikanth and Rusmevichientong, Paat , title =. Management Science , year =

    work page

  53. [53]

    Operations Research , year =

    work page

  54. [54]

    Journal of Revenue and Pricing Management , year =

    Hajmirzaei, Milad and Ziarati, Koorush and Nikseresht, Alireza , title =. Journal of Revenue and Pricing Management , year =

    work page

  55. [55]

    Operations Research , year =

    L. Operations Research , year =

    work page

  56. [56]

    Operations Research , year =

    Feldman, Jacob and Paul, Alice and Topaloglu, Huseyin , title =. Operations Research , year =

    work page

  57. [57]

    Manufacturing & Service Operations Management , year =

    Honhon, Dorothee and Jonnalagedda, Sreelata and Pan, Xiajun Amy , title =. Manufacturing & Service Operations Management , year =

    work page

  58. [58]

    Mahajan, S. and. Operations Research , year =

    work page

  59. [59]

    and Jagabathula, Srikanth and Shah, Devavrat , title =

    Farias, Vivek F. and Jagabathula, Srikanth and Shah, Devavrat , title =. Management Science , year =

    work page

  60. [60]

    Operations Research , year =

    Blanchet, Jose and Gallego, Guillermo and Goyal, Vineet , title =. Operations Research , year =

    work page

  61. [61]

    2020 , pages =

    Tulabandhula, Theja and Sinha, Deekska and Patidar, Prasoon , title =. 2020 , pages =

    work page 2020

  62. [62]

    and Kumar, Ravi and Tomkins, Andrew , title =

    Benson, Austin R. and Kumar, Ravi and Tomkins, Andrew , title =. WSDM 2018 -- Proceedings of the 11th ACM International Conference on Web Search and Data Mining , year =

    work page 2018

  63. [63]

    Web and Internet Economics , year =

    Immorlica, Nicole and Lucier, Brendan and Mao, Jieming and Syrgkanis, Vasilis and Tzamos, Christos , title =. Web and Internet Economics , year =

    work page

  64. [64]

    and Blei, David and Athey, Susan , title =

    Donnelly, Rob and Ruiz, Francisco R. and Blei, David and Athey, Susan , title =. 2019 , pages =

    work page 2019

  65. [65]

    Manufacturing and Service Operations Management , title =

    Vulcano, Gustavo and. Manufacturing and Service Operations Management , title =. 2010 , number =

    work page 2010

  66. [66]

    , journal =

    Lee, Joonkyum and Gaur, Vishal and Muthulingam, Suresh and Swisher, Gary F. , journal =. 2016 , number =

    work page 2016

  67. [67]

    SSRN Electronic Journal , pages =

    Berbeglia, Gerardo and Venkataraman, Ashwin , title =. SSRN Electronic Journal , pages =. 2018 , arxivid =. doi:10.2139/ssrn.3136227 , issn =

    work page doi:10.2139/ssrn.3136227 2018

  68. [68]

    2022 , url =

    Xin Chen and Jiachun Li and Menglong Li and Tiancheng Zhao and Yuan Zhou , title =. 2022 , url =

    work page 2022

  69. [69]

    Manufacturing & Service Operations Management , volume =

    Jasin, Stefanus and Lyu, Chengyi and Najafi, Sajjad and Zhang, Huanan , title =. Manufacturing & Service Operations Management , volume =

    work page

  70. [70]

    Manufacturing and Service Operations Management , year =

    Theja Tulabandhula and Deeksha Sinha and Saketh Reddy Karra and Prasoon Patidar , title =. Manufacturing and Service Operations Management , year =

    work page

  71. [71]

    Operations Research , year =

    Yicheng Bai and Jacob Feldman and Danny Segev and Huseyin Topaloglu and Laura Wagner , title =. Operations Research , year =

    work page

  72. [72]

    Production and Operations Management , year =

    Hongyuan Lin and Xiaobo Li and Lixia Wu , title =. Production and Operations Management , year =

    work page

  73. [73]

    2020 , url =

    Zeyu Sun and Selin Damla Ahipasaoglu and Xiaobo Li and Yanqiu Ruan , title =. 2020 , url =

    work page 2020

  74. [74]

    Column generation , pages=

    Shortest path problems with resource constraints , author=. Column generation , pages=. 2005 , publisher=

    work page 2005

  75. [75]

    Mathematical Programming Computation , volume=

    Improved branch-cut-and-price for capacitated vehicle routing , author=. Mathematical Programming Computation , volume=. 2017 , publisher=

    work page 2017

  76. [76]

    INFORMS Journal on Computing , volume=

    Path-reduced costs for eliminating arcs in routing and scheduling , author=. INFORMS Journal on Computing , volume=. 2010 , publisher=

    work page 2010