检索结果-内蒙古大学图书馆

On the estimation of discrete choice models to capture irrational customer behaviors

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Jena, Sanjay Dominik Lodi, Andrea Sole, Claudio Canada Excellence Research Chair in Data-Science for Real-time Decision-Making Polytechnique Montréal

The Random Utility Maximization model is by far the most adopted framework to estimate consumer choice behavior. However, behavioral economics has provided strong empirical evidence of irrational choice behavior, such as halo effects, that are incompatible with this framework. Models belonging to the Random Utility Maximization family may therefore not accurately capture such irrational behavior. Hence, more general choice models, overcoming such limitations, have been proposed. However, the flexibility of such models comes at the price of increased risk of overfitting. As such, estimating such models remains a challenge. In this work, we propose an estimation method for the recently proposed Generalized Stochastic Preference choice model, which subsumes the family of Random Utility Maximization models and is capable of capturing halo effects. Specifically, we show how to use partially-ranked preferences to efficiently model rational and irrational customer types from transaction data. Our estimation procedure is based on column generation, where relevant customer types are efficiently extracted by expanding a tree-like data structure containing the customer behaviors. Further, we propose a new dominance rule among customer types whose effect is to prioritize low orders of interactions among products. An extensive set of experiments assesses the predictive accuracy of the proposed approach. Our results show that accounting for irrational preferences can boost predictive accuracy by 12.5% on average, when tested on a real-world dataset from a large chain of grocery and drug stores. Copyright © 2021, The Authors. All rights reserved.

关键词： Sales

Ecole: A library for learning inside MILP solvers

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Prouvost, Antoine Dumouchelle, Justin Gasse, Maxime Chételat, Didier Lodi, Andrea Canada Excellence Research Department in Data Science for Decision Making École Polytechnique de Montréal Canada Mila Quebec Artificial Intelligence Institute Italy

In this paper we describe Ecole (Extensible Combinatorial Optimization Learning Environments), a library to facilitate integration of machine learning in combinatorial optimization solvers. It exposes sequential decision making that must be performed in the process of solving as Markov decision processes. This means that, rather than trying to predict solutions to combinatorial optimization problems directly, Ecole allows machine learning to work in cooperation with a state-of-the-art a mixed-integer linear programming solver that acts as a controllable algorithm. Ecole provides a collection of computationally efficient, ready to use learning environments, which are also easy to extend to define novel training tasks. Documentation and code can be found at https://***. © 2021, CC BY.

关键词： Combinatorial optimization

An exact algorithm for large-scale non-convex quadratic facility location

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Zetina, Carlos Armando Contreras, Ivan Jayaswal, Sachin IVADO Labs and Canada Excellence Research Chair in Data Science for Real-Time Decision-Making Polytechnique Montréal Canada MontrealH3G 1M8 Canada Indian Institute of Management Ahmedabad Gujarat India

We study a general class of quadratic capacitated p-location problems facility location problems with single assignment where a non-separable, non-convex, quadratic term is introduced in the objective function to account for the interaction cost between facilities and customer assignments. This problem has many applications in the field of transportation and logistics where its most well-known special case is the single-allocation hub location problem and its many variants. The non-convex, binary quadratic program is linearized by applying a reformulation-linearization technique and the resulting continuous auxiliary variables are projected out using Benders decomposition. The obtained Benders reformulation is then solved using an exact branch-and-cut algorithm that exploits the underlying network flow structure of the decomposed separation subproblems to efficiently generate strong Pareto-optimal Benders cuts. Additional enhancements such as a matheuristic, a partial enumeration procedure, and variable elimination tests are also embedded in the proposed algorithmic framework. Extensive computational experiments on benchmark instances (with up to 500 nodes) and on a new set of instances (with up to 1,000 nodes) of four variants of single-allocation hub location problems confirm the algorithm’s ability to scale to large-scale *** Codes 90B80 (Primary), 90B06 (Secondary). © 2021, CC BY-NC-SA.

关键词： Quadratic programming

Guidelines for the computational testing of machine learning approaches to vehicle routing problems

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Accorsi, Luca Lodi, Andrea Vigo, Daniele Department of Electrical Electronic and Information Engineering "G. Marconi" University of Bologna Italy Canada Excellence Research Chair in Data Science for Decision Making École Polytechnique de Montréal Canada Mila Quebec Artificial Intelligence Institute Canada CIRI ICT University of Bologna Italy

Despite the extensive research efforts and the remarkable results obtained on Vehicle Routing Problems (VRP) by using algorithms proposed by the Machine Learning community that are partially or entirely based on data-driven analysis, most of these approaches are still seldom employed by the Operations research (OR) community. Among the possible causes, we believe, the different approach to the computational evaluation of the proposed methods may play a major role. With the current work, we want to highlight a number of challenges (and possible ways to handle them) arising during the computational studies of heuristic approaches to VRPs that, if appropriately addressed, may produce a computational study having the characteristics of those presented in OR papers, thus hopefully promoting the collaboration between the two communities. © 2021, CC BY-NC-SA.

关键词： Operations research

An Exact Method for (Constrained) Assortment Optimization Problems with Product Costs

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Leitner, Markus Lodi, Andrea Roberti, Roberto Sole, Claudio Department of Operations Analytics Vrije Universiteit Amsterdam Netherlands Jacobs Technion-Cornell Institute Cornell Tech and Technion - IIT United States Department of Information Engineering University of Padova Italy Canada Excellence Research Chair in Data-Science for Real-time Decision-Making Polytechnique Montréal Canada

We study the problem of optimizing assortment decisions in the presence of product-specific costs when customers choose according to a multinomial logit model. This problem is NP-hard and approximate solutions methods have been proposed in the literature to obtain both lower and upper bounds in a tractable manner. We propose the first exact solution method for this problem and show that provably optimal assortments of instances with up to one thousand products can be found, on average, in about two tenths of a second. In particular, we propose a bounding procedure based on the approximation method of Feldman and Topaloglu (2015a) to provide tight lower and upper bounds at a fraction of their computing times. We show how these bounds can be used to effectively identify an optimal assortment. We also describe how to adapt our approach to handle cardinality or space/resource capacity constraints on the assortment as well as assortment optimization under a mixed-multinomial logit model. In both cases, our solution method provides significant computational boosts compared to exact methods from the literature. Copyright © 2021, The Authors. All rights reserved.

关键词： Approximation theory

Dynamic Rebalancing for Bike-Sharing Systems Under Inventory Interval and Target Predictions

学校读者我要写书评

暂无评论

SSRN

SSRN 2023年

作者： Jiaqi, Liang Silva, Maria Clara Martins Daniel, Aloise Jena, Sanjay Dominik Polytechnique Montréal 2500 Chemin de Polytechnique MontréalH3T 1J4 Canada School of Management Université du Québec à Montréal 315 Rue Sainte-Catherine Est MontréalH2X 3X2 Canada 2920 Chemin de la Tour MontréalH3T 1J4 Canada Canada Excellence Research Chair in Data-Science for Real-time Decision-Making 2500 Chemin de Polytechnique MontréalH3T 1J4 Canada 2920 Chemin de la Tour MontréalH3T 1N8 Canada

Bike-sharing systems have become a popular transportation alternative. Unfortunately, station networks are often unbalanced, with some stations being empty, while others being congested. Given the complexity of the underlying planning problems to rebalance station inventories via trucks, many mathematical optimizations models have been proposed, mostly focusing on minimizing the unmet demand. This work explores the benefits of two alternative objectives, which minimize the deviation from an inventory interval and a target inventory, respectively. While the concepts of inventory intervals and targets better fit the planning practices of many system operators, they also naturally introduce a buffer into the station inventory, therefore better responding to stochastic demand fluctuations. We report on extensive computational experiments, evaluating the entire pipeline required for an automatized and data-driven rebalancing process: the use of synthetic and real-world data that relies on varying weather conditions, the prediction of demand and the computation of inventory intervals and targets, different reoptimization modes throughout the planning horizon, and an evaluation within a fine-grained simulator. Results allow for unanimous conclusions, indicating that the proposed approaches reduce unmet demand by up to 34% over classical models. © 2023, The Authors. All rights reserved.

关键词： Stochastic systems

COMPUTING NASH EQUILIBRIA FOR INTEGER PROGRAMMING GAMES∗

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Carvalho, Margarida Lodi, Andrea Pedroso, João Pedro CIRRELT and Département d’Informatique et de Recherche Opérationnelle Université de Montréal Canada Canada Excellence Research Chair in Data Science for Real-Time Decision-Making Polytechnique de Montréal Canada INESC TEC Departamento de Ciência de Computadores Faculdade de Ciências Universidade do Porto Portugal

The recently defined class of integer programming games (IPG) models situations where multiple self-interested decision makers interact, with their strategy sets represented by a finite set of linear constraints together with integer requirements. Many real-world problems can suitably be fit in this class, and hence anticipating IPG outcomes is of crucial value for policy makers and regulators. Nash equilibria have been widely accepted as the solution concept of a game. Consequently, their computation provides a reasonable prediction of games outcome. In this paper, we start by showing the computational complexity of deciding the existence of a Nash equilibrium for an IPG. Then, using sufficient conditions for their existence, we develop two general algorithmic approaches that are guaranteed to approximate an equilibrium under mild conditions. We also showcase how our methodology can be changed to determine other equilibria definitions. The performance of our methods is analysed through computational experiments in a knapsack game, a competitive lot-sizing game and a kidney exchange game. To the best of our knowledge, this is the first time that equilibria computation methods for general integer programming games have been designed and computationally tested. Copyright © 2020, The Authors. All rights reserved.

关键词： Integer programming

A solution to a Partitioned Balanced Tournament Design of side 11

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Croce, Federico Della Dragotto, Gabriele Salassa, Fabio Dipartimento di Ingegneria Gestionale e della Produzione Politecnico di Torino Italy CNR IEIIT Torino Italy Canada Excellence Research Chair in Data Science for Real-time Decision-making École Polytechnique de Montréal Canada

关键词： Combinatorial optimization

GAME THEORETICAL ANALYSIS OF KIDNEY EXCHANGE PROGRAMS

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Carvalho, Margarida Lodi, Andrea Cirrelt Département d'Informatique et de Recherche Opérationnelle Université de Montréal Canada Canada Excellence Research in Data Science for Real-Time Decision-Making Polytechnique de Montréal Canada

The goal of a kidney exchange program (KEP) is to maximize number of transplants within a pool of incompatible patient-donor pairs by exchanging donors. A KEP can be modelled as a maximum matching problem in a graph. A KEP between incompatible patient-donor from pools of several hospitals, regions or countries has the potential to increase the number of transplants. These entities aim is to maximize the transplant benefit for their patients, which can lead to strategic behaviours. Recently, this was formulated as a non-cooperative two-player game and the game solutions (equilibria) were characterized when the entities objective function is the number of their patients receiving a kidney. In this paper, we generalize these results for N-players and discuss the impact in the game solutions when transplant information quality is introduced. Furthermore, the game theory model is analyzed through computational experiments on instances generated through the canada Kidney Paired Donation Program. These experiments highlighting the importance of using the concept of Nash equilibrium, as well as, the anticipation of the necessity to further research for supporting police makers once measures on transplant quality are *** Codes 91-XX, 05Cxx, 90-XX Copyright © 2019, The Authors. All rights reserved.

关键词： Game theory