tag:www.gerad.ca,2005:/fr/papersCahiers du GERAD2022-09-26T10:46:52-04:0020tag:www.gerad.ca,2005:Paper/29672022-09-23T16:51:26-04:002022-09-26T10:46:52-04:00G-2022-40 : Remanufacturing with innovative features: A strategic analysisCan Baris Cetin, Georges Zaccour
<p>In this study, we investigate the best remanufacturing strategy for the original equipment manufacturer (OEM) and independent remanufacturer (IR) in an innovative industry where the consumer valuation of the products increases with the level of innovation, and we characterize how the best strategy changes with the identity of the remanufacturer. Our work differs from existing articles that investigate the remanufacturing strategy in the presence of quality decisions, by actively including the innovative features in the remanufactured products, as opposed to passively carrying over product quality to the remanufactured products. We consider three remanufacturing strategies: (i) not remanufacturing, (ii) remanufacturing without adding innovative features, and (iii) remanufacturing adding innovative features (upgrading). To analyze the problem, we create a single-period model where the OEM determines the level of innovation and the quantity of new products, in both competitive settings, and either the OEM or IR determines the remanufacturing quantity depending on the competitive setting. We investigate how the firms' environmental impact and the consumer surplus are affected by the competition and the remanufacturing strategy.</p>
2022-09-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/26132018-10-04T09:36:00-04:002022-09-26T10:49:17-04:00G-2018-68 : Valuing corporate securities when the firm's assets are illiquidHatem Ben-Ameur, Tarek Fakhfakh, Alexandre Roch
<p>We use stochastic dynamic programming to design and solve an extended
structural setting for which the illiquidity of the firm's assets under
liquidation is interpreted as an intangible corporate security. This asset
tends to reduce bond values, augment yield spreads, and, thus, partially
explain the credit-spread puzzle. To assess our construction, we provide a
sensitivity analysis of the values of corporate securities with respect to
the illiquidity parameter.</p>
2018-09-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29662022-09-23T16:48:37-04:002022-09-26T10:47:17-04:00G-2022-35 : On GSOR, the generalized successive overrelaxation method for double saddle-point problemsNa Huang, Yu-Dong Dai, Dominique Orban, Michael A. Saunders
<p>Nous considérons la méthode de surrelaxation successive généralisée (GSOR) pour la résolution
d’une classe de systèmes de points de selle à trois par trois blocs. Sur base des conditions
nécessaires et suffisantes pour que les racines d'un polynôme de degré trois soient de module
inférieur à l'unité, nous établissons la convergence de la méthode sous des hypothèses
raisonnables. Nous analysons également une calsse de préconditionneurs triangulaires
inférieurs par blocs induits par GSOR et dérivons des bornes spectrales explicites et fines pour
les matrices préconditionnées. Nous présentons des résultats numériques sur des problèmes de
crystaux liquides et du flux couplé de Stokes-Darcy, et illustrons l'utilité de GSOR.</p>
2022-08-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29652022-09-23T16:45:31-04:002022-09-26T10:47:44-04:00G-2022-34 : Thirty years of academic financeDavid Ardia, Keven Bluteau, Mohammad-Abbas Meghani
<p>We study how the financial literature has evolved in scale, research team composition, and article topicality across 32 finance-focused academic journals from 1992 to 2021.
We document that the field has vastly expanded regarding outlets and published articles. Teams have become larger, and the proportion of women participating in research has increased significantly. Using the Structural Topic Model, we identify 45 topics discussed in the literature. We investigate the topic coverage of individual journals and can identify highly specialized and generalist outlets, but our analyses reveal that most journals have covered more topics over time, thus becoming more generalist. Finally, we find that articles with at least one woman author focus more on topics related to social and governance aspects of corporate finance. We also find that teams with at least one top-tier institution scholar tend to focus more on theoretical aspects of finance.</p>
2022-08-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29642022-09-23T16:41:45-04:002022-09-26T10:48:03-04:00G-2022-33 : Hybrid storage system control for real-time power balancing in a hybrid renewable energy systemImen Jendoubi, François Bouffard
<p>Les systèmes de production d'énergie renouvelables hybrides (SPERH), où l'on peut trouver deux ou plusieurs moyens de production d'énergie renouvelables co-localisées, sont prometteurs car ils permettent de mettre en commun les aspects complémentaires de différentes sources d'énergie. En revanche, l'incertitude associée au niveau de production de ces systèmes requiert qu'ils aient recours à des ressources, tels les systèmes de stockage d'énergie (SSE), afin de contrôler l'équilibre entre la production et la charge. Cet article propose une approche de commande basée sur les données d'un SSE hybride -c'est à dire un SSE possèdant plusieurs médiums de stockage- dans le contexte d'un SPERH. Son objectif est de maintenir l'équilibre entre la production et la charge du SPERH en temps réel tout en maximisant l'apport de production renouvelable. L'approche de commande proposée est basée sur l'apprentissage par renforcement multi-agent profond. En comparant cette approche aux autres méthodes utilisées en pratique, c'est-à-dire la commande par modèle prédictif et la commande à base de règles, on constate sa performance selon une gamme de critères rigoureux afin d'y voir les compromis associés pour chaque approche. Parmi ces critères on retrouve la fiabilité de service, l'impact environnemental, la gestion de l'incertitude, la durée de vie des systèmes de stockage par batteries, l'effort de calcul, les besoins de moyens de télécommunication, les habiletés adaptatives et les capacités d'anticipation. L'analyse met en lumière les bénéfices des SSE hybrides au sein d'un SPERH et les résultats expérimentaux démontrent comment notre approche basée sur les données peut performer au même niveaux que les méthodes de pointe. De plus, dépendamment des caractéristiques des systèmes et des priorités d'exploitation, la sélection d'une approche de commande présente un compromis entre différents critères qui doivent être pris en compte de manière conjointe. </p>
2022-08-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29622022-08-15T14:33:32-04:002022-08-15T14:33:33-04:00G-2022-32 : Optimal localizability criterion for positioning with distance-deteriorated relative measurementsJustin Cano, Gaël Pagès, Éric Chaumette, Jérôme Le Ny
<p>Position estimation in Multi-Robot Systems (MRS) relies on relative angle or
distance measurements between the robots, which generally deteriorate as
distances increase. Moreover, the localization accuracy is strongly influenced
both by the quality of the raw measurements but also by the overall
geometry of the network. In this paper, we design a cost function that accounts for these two issues
and can be used to develop motion planning algorithms that optimize the
localizability in MRS, i.e., the ability of individual robots to localize
themselves accurately. This cost function is based on computing new
Cramér Rao Lower Bounds characterizing the achievable positioning
performance with range and angle measurements that deteriorate with increasing
distances. We describe a gradient-based motion-planning algorithm for
MRS deployment that can be implemented in a distributed manner,
as well as a non-myopic strategy to escape local minima.
Finally, we test the proposed methodology experimentally for range measurements
obtained using ultra-wide band transceivers and illustrate the improvements
resulting from leveraging the more accurate measurement model in the
robot placement algorithms.</p>
2022-08-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29612022-08-15T14:29:19-04:002022-08-15T14:29:19-04:00G-2022-31 : Learning to branch for the crew pairing problemPierre Pereira, Emeric Courtade, Daniel Aloise, Frédéric Quesnel, François Soumis, Yassine Yaakoubi
<p>Crew pairing problems (CPP) are regularly solved by airlines to produce crew schedules.
The goal of CPPs is to find a set of pairings (sequence of flights and rests forming one or more workdays) that cover all flights in a given period at a minimum cost.
The CPP is a NP-hard combinatorial problem that is usually solved approximately using a branch-and-price heuristic.
A common branching heuristics selects the closest-to-one pairing variable and fixes it without backtracking, which allows finding good solutions quickly.
By contrast, variable selection strategies based on strong branching typically produce better solutions but are computationally prohibitive.
This paper explores the possibility of learning efficient branching strategies for diving heuristics from strong branching decisions.
To help the learning process, we propose a new normalisation of the branching scores which is able to better distinguish the good and bad branching candidates.
Our results demonstrate that our learnt strategies make better branching decisions than the greedy strategy while executing in approximately the same computational time.</p>
2022-07-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29602022-08-15T14:20:51-04:002022-08-15T14:21:02-04:00G-2022-30 : Increasing schedule reliability in the multi-depot vehicle scheduling problem with stochastic travel timeLéa Ricard, Guy Desaulniers, Andrea Lodi, Louis-Martin Rousseau
<p>The multi-depot scheduling problem (MDVSP) is one of the most studied problem in public transport service planning. It consists of assigning buses to each timetabled trip while respecting vehicle availability at each depot. Although service quality, and especially reliability, is the core of most transport agencies, the MDVSP is more often than not solved solely in a cost-efficient way. This work introduces a data-driven model to the reliable MDVSP with stochastic travel time (R-MDVSP-STT). The reliability of a schedule is assessed and accounted for by propagating delays using the probability mass function of the travel time of each timetabled trip. We propose a heuristic branch-and-price algorithm to solve this problem and a labeling algorithm with stochastic dominance criterion for the associated subproblems. The solutions obtained are compared based on three passenger-oriented metrics - under normal and extraordinary circumstances. Computational results on real-life instances show that our method can efficiently find good trade-offs between operational costs and reliability, improving the reliability of the solutions with little cost increase.</p>
2022-07-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29582022-07-08T10:27:34-04:002022-08-15T15:00:31-04:00G-2022-29 : Learning to enumerate shifts for large-scale flexible personnel scheduling problemsFarin Rastgar, Claudio Contardo, Guy Desaulniers, Maxime Gasse
<p>Personnel scheduling consists in determining employee work schedules (sequences of work shifts and days off) to cover the demands of multiple jobs over a planning horizon. We consider finding a near-optimal set of personnel schedules via the solution of a generalized set-covering model with side constraints in a flexible context where a large number of potential shifts can be considered as in the retail industry. Commercial solvers applied to this model often require very long computational times for practical problem sizes, and as such rely on enumeration heuristics for filtering non-promising shifts/schedules and, thus, reducing the problem size. We propose deep learning-based heuristics to drive the enumeration of promising potential shifts based on the information collected from previously solved instances. Our models predict a subset of time points at which promising shifts are more likely to either start or end, thus filtering out those that do not start nor end at those time points. Our computational results on real-life instances show that personnel scheduling problems can be solved considerably faster with an acceptable optimality gap if shifts are enumerated according to the time points predicted by our models.</p>
2022-07-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29632022-09-23T16:32:51-04:002022-09-26T10:48:32-04:00G-2022-26 : Foreseeing the worst: Forecasting electricity DART spikesRémi Galarneau-Vincent, Geneviève Gauthier, Frédéric Godin
<p>Statistical learning models are proposed for the prediction of the probability of a spike in the electricity DART (day-ahead minus real-time price) spread. Assessing the likelihood of DART spikes is of paramount importance for virtual bidders, among others. The model's performance is evaluated on historical data for the Long Island zone of the New York Independent System Operator (NYISO). A tailored feature set encompassing novel engineered features is designed. Such a set of features makes it possible to achieve excellent predictive performance and discriminatory power. Results are shown to be robust to the choice of the predictive algorithm. Lastly, the benefits of forecasting the spikes are illustrated through a trading exercise, confirming that trading strategies employing the model predicted probabilities as a signal generate consistent profits. </p>
2022-06-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29572022-07-08T10:23:54-04:002022-08-15T15:00:53-04:00G-2022-28 : A heuristic approach for the integrated production-transportation problem with process flexibilityDesiree Maldonado Carvalho, Raf Jans, Silvio Alexandre de Araujo, Diego Fiorotto
<p>We study an integrated multi-product production and distribution problem considering a network of multiple plants and customers, who are geographically dispersed, with direct shipment from the plants to the costumers. In addition to the decisions on production and distribution, a decision needs to be taken on the level of process flexibility in the network, i.e., which products can be produced in which plants. There is a clear trade-off between these decisions. On one hand, a network with total flexibility where each plant can produce all types of products allows for lower transportation costs, but requires large investments in flexibility and frequent setups. On the other hand, a network with a limited amount of flexibility where each plant produce only few products, will increase the transportation costs, but requires a lower investment in flexibility. We model this problem as an extension of the capacitated lot-sizing problem. We limit the investment in flexibility by a budget constraint and minimize the operational costs. Varying this budget allows us to analyze different levels of flexibility. In this paper, we propose mathematical models and a hybrid solution method that combines a mixed integer programming-based approach and a kernel search heuristic. Our computational results using data sets from the literature show that the proposed hybrid method produces on average better solutions with significantly lower computational times when compared with the results produced by a state-of-the-art optimization software. Additional computational results are presented by varying key parameters and analyzing their impact on the value of flexibility. These computational experiments indicate that some of the main managerial insights which were derived in the literature for the case without transportation costs are no longer valid when we consider transportation costs.</p>
2022-06-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29562022-07-08T10:19:31-04:002022-08-22T15:59:56-04:00G-2022-27 : A stochastic proximal method for nonsmooth regularized finite sum optimizationDounia Lakhmiri, Dominique Orban, Andrea Lodi
<p>We consider the problem of training a deep neural network with nonsmooth regularization to retrieve a sparse and efficient sub-structure. Our regularizer is only assumed to be lower semi-continuous and prox-bounded. We combine an adaptive quadratic regularization approach with proximal stochastic gradient principles to derive a new solver, called SR2, whose convergence
and worst-case complexity are established without knowledge or approximation of the gradient's Lipschitz constant. We formulate a stopping criteria that ensures an appropriate first-order stationarity measure converges to zero under certain conditions.
We establish a worst-case iteration complexity of <code>\(\mathcal{O}(\epsilon^{-2})\)</code> that matches those of related methods like ProxGEN, where the learning rate is assumed to be related to the Lipschitz constant.
Our experiments on network instances trained on CIFAR-10 and CIFAR-100 with <code>\(\ell_1\)</code> and <code>\(\ell_0\)</code> regularizations show that SR2 consistently achieves higher sparsity and accuracy than related methods such as ProxGEN and ProxSGD.</p>
2022-06-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29552022-07-08T10:14:58-04:002022-08-15T15:01:35-04:00G-2022-25 : A semi-conjugate gradient method for solving unsymmetric positive definite linear systemsNa Huang, Yu-Dong Dai, Dominique Orban, Michael A. Saunders
<p>The conjugate gradient (CG) method is a classic Krylov subspace method for solving symmetric positive definite linear systems.
We introduce an analogous semi-conjugate gradient (SCG) method for unsymmetric positive definite linear systems. Unlike CG, SCG requires the solution of a lower triangular linear system to produce each semi-conjugate direction. We prove that SCG is theoretically equivalent to the full orthogonalization method (FOM), which is based on the Arnoldi process and converges in a finite number of steps. Because SCG's triangular system increases in size each iteration, we study a sliding window implementation (SWI) to improve efficiency, and show that the directions produced are still locally semi-conjugate. A counter-example illustrates that SWI is different from the direct incomplete orthogonalization method (DIOM), which is FOM with a sliding window. Numerical experiments from the convection-diffusion equation and other applications show that SCG is robust and that the sliding window implementation SWI allows SCG to solve large systems efficiently. </p>
2022-06-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29542022-07-08T10:11:30-04:002022-09-01T15:37:58-04:00G-2022-24 : How easy is it for investment managers to deploy their talent in green and brown stocks?David Ardia, Keven Bluteau, Tien Duy Tran
<p>We explore the realized alpha-performance heterogeneity in green and brown stocks' universes using the peer performance ratios of Ardia and Boudt(2018). Focusing on S&P 500 index firms over 2014-2020 and defining peer groups in terms of firms' greenhouse gas emission levels, we find that, on average, about 20% of the stocks differentiate themselves from their peers in terms of future performance. We see a much higher time-variation in this opportunity set within brown stocks. Furthermore, the performance heterogeneity has decreased over time, especially for green stocks, implying that it is now more difficult for investment managers to deploy their skills when choosing among low-GHG intensity stocks.</p>
2022-06-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29592022-08-15T14:12:12-04:002022-08-15T14:12:12-04:00G-2022-23 : Venturing into uncharted territory: An extensible implied volatility surface modelPascal François, Rémi Galarneau-Vincent, Geneviève Gauthier, Frédéric Godin
<p>A new factor-based representation of implied volatility surfaces is proposed. The factors adequately capture the moneyness and maturity slopes, the smile attenuation, and the smirk. Furthermore, the implied volatility specification is twice continuously differentiable and well behaved asymptotically, allowing for clean interpolation and extrapolation over a wide range of moneyness and maturity. Fitting performance on S&P 500 options compares favorably with existing benchmarks. The benefits of a smoothed implied volatility surface are illustrated through the valuation of illiquid index derivatives, the extraction of the risk-neutral density and risk-neutral moments, and the calculation of option price sensitivities.</p>
2022-05-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29472022-06-14T14:37:42-04:002022-06-14T14:37:42-04:00G-2022-22 : A fast dual bound for power allocationAndré Girard
<p>Nous proposons dans cet article un algorithme rapide pour calculer une
borne supérieure au problème de la gestion de la puissance des
utilisateurs d'un ensemble de canaux sans fil. Nous
définissons un problème équivalent et montrons comment le calcul de la
fonction duale de ce problème se décompose en sous-problèmes non
convexes en deux variables. Nous calculons ensuite analytiquement la solution
optimale des sous-problèmes, ce qui permet
un calcul rapide de la fonction duale.</p>
2022-05-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29462022-06-14T14:34:58-04:002022-06-14T14:35:25-04:00G-2022-21 : Dynamic pricing in the presence of social externalities and reference-price effectJafar Chaab, Georges Zaccour
<p>This paper considers the pricing of a new product in the face of sophisticated consumer behaviors. At the individual level, consumers are forward-looking, whereby they may wait strategically for intertemporal arbitrage. Additionally, and in line with prospect theory, consumers might also look back to form a reference-price point with which they can compare the current price. Consumers are assumed to be loss averse where losses resonate more than gains. At the aggregate level, we account for the role of social influences in the form of externalities in consumers' adoption decision. We develop progressively different nested models to account for impact of each behavior. We find that skimming pricing strategy is advocated by reference-dependent loss-averse behaviors, whereas the penetration pricing strategy functions better in the presence of strong forward-looking behavior and social influences.</p>
2022-05-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29322022-03-25T17:04:38-04:002022-06-14T14:04:05-04:00G-2022-02 : Approximated multi-agent fitted Q iterationAntoine Lesage-Landry, Duncan Callaway
<p>We formulate an efficient approximation for multi-agent batch reinforcement learning, the approximated multi-agent fitted Q iteration (AMAFQI). We present a detailed derivation of our approach. We propose an iterative policy search and show that it yields a greedy policy with respect to multiple approximations of the centralized, learned Q-function. In each iteration and policy evaluation, AMAFQI requires a number of computations that scales linearly with the number of agents whereas the analogous number of computations increase exponentially for the fitted Q iteration (FQI), a commonly used approaches in batch reinforcement learning. This property of AMAFQI is fundamental for the design of a tractable multi-agent approach. We evaluate the performance of AMAFQI and compare it to FQI in numerical simulations. The simulations illustrate the significant computation time reduction when using AMAFQI instead of FQI in multi-agent problems and corroborate the similar performance of both approaches.</p>
2022-01-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/28872021-10-12T15:01:25-04:002022-06-14T14:05:24-04:00G-2021-48 : Predicting COVID-19 incidences from patients? Viral load using deep-learningAthar Khalil, Khalil Al Handawi, Ibrahim Chamseddine, Zeina Mohsen, Afif Abdel Nour, Rita Feghali, Michael Kokkolaras
<p>The transmission of the contagious Coronavirus disease (COVID-19) is highly dependent on individual viral dynamics. Reverse-transcription quantitative polymerase chain reaction (RT-qPCR) tests used for diagnosing COVID-19 provide a semi-quantitative measurement of viral load within the infected host in the form of a Cycle treshold (Ct) value. We solicited Ct values sampled from a cross-sectional patient cohort at Rafik Hariri University Hospital to now-cast COVID-19 incidences in Lebanon. Our patient cohort of 9531 patients, retrieved from a single representative cross-sectional virology test center in Lebanon, revealed that when the mean Ct value of a daily sample of patients is low, an increase in positive COVID-19 case counts is observed in Lebanon. A subset of the data was used to train several machine learning models and tune their hyperparameters with respect to the validation error. Unseen data unused during model development is used to report the models' test error. Support vector machine regression performed well on the unseen data and was able to provide predictions for the positive case counts in Lebanon over the span of 7 days. The models are a first attempt at capturing the interaction between cross-sectional Ct values and the pandemic trajectory including temporal effects that arise from population dynamics. The model has potential applications for predicting COVID-19 incidences in other countries and in assessing post-vaccination policies. Apart from emphasizing patient responsibility in adopting early testing practices, this study proposed and validated viral load measurement as a relevant input that can enhance the predictive accuracy of viral disease now-casting models.</p>
2021-08-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29532022-07-08T10:02:13-04:002022-08-15T15:02:21-04:00G-2022-16 : A logistic regressionand linear programming approach for multi-skill staffing optimization in call centersThuy Anh Ta, Tien Mai, Fabian Bastin, Pierre L'Ecuyer
<p>We study a staffing optimization problem in multi-skill call centers. The objective is to minimize the total cost of agents under some quality of service (QoS) constraints. The key challenge lies in the fact that the QoS functions have no closed-form and need to be approximated by simulation.
In this paper we propose a new way to approximate the QoS functions by logistic functions and design a new algorithm that combines logistic regression, cut generations and logistic-based local search to efficiently find good staffing solutions. We report computational results using examples up to 65 call types and 89 agent groups showing that our approach performs well in in practice, in terms of solution quality and computing time.</p>
2022-04-01GERADinfo@gerad.ca