Exécution de notre outil de synthèse sur un nouvel article

Vérifiez l’article ci-dessous, puis lancez sa synthèse.


Alternative Computational Formulations for Testing Discrete-Choice Random Utility Models: Half-Space and Network-Flow Formulations

Haoge Chang, Kota Saito, Mingxi Zhu

Licence : CC BY 4.0

Résumé : This paper develops computational algorithms for testing discrete-choice random utility models (RUM). The set of RUM-consistent choice probabilities forms a polytope, and existing computational methods rely on its vertex representation. We exploit alternative half-space (Block--Marschak inequalities) and network-flow representations to develop two methods based on the alternating direction method of multipliers and a flow-based column-generation algorithm. Compared with current vertex-based methods, our algorithms are better suited to GPU implementation. We establish convergence guarantees and provide optimality certificates for all three algorithms. The resulting algorithms achieve $100$--$600\times$ speedups over existing methods. The solver based on our methods is publicly available on Github at \href{https://github.com/mingxiz/d-rum-testing-gpu}{\texttt{d-rum-testing-gpu}}.

Soumis à arXiv le 14 Nov. 2026