tag:www.gerad.ca,2005:/fr/papersCahiers du GERAD2023-03-30T10:16:14-04:0020tag:www.gerad.ca,2005:Paper/29932023-03-30T09:29:03-04:002023-03-30T10:16:14-04:00G-2023-03 : Assessing electric mobility and renewable energy synergy in a small New Caledonia island communityFrédéric Babonneau, David Chotard, Alain Haurie
<p>In this paper, we evaluate the synergy between variable renewable energy (VRE), electric mobility, and Vehicle to Grid (V2G) deployment for a small community transitioning to a low-carbon economy. We propose an integrated deterministic modeling approach that accurately describes electric mobility activity within the electric grid in the ETEM-SG long-term capacity expansion model. This approach allowed us to keep the entire approach in the linear programming domain. We then perform a scenario analysis on the Isle of Pines case. The results show that V2G is essential for electric vehicles to make a positive contribution to the electric system by providing a supply-demand balance service. The deployment of electric vehicles allows reaching a VRE penetration rate of up to 94%, at no additional cost compared to a solution without electric vehicles, and even with a global-cost reduction of up to 5.3% thanks to a decrease of the capacity of stationary battery packs needed for storage.</p>
2023-02-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29922023-03-28T16:37:40-04:002023-03-30T09:13:46-04:00G-2023-04 : Factor exposure heterogeneity in green and brown stocksDavid Ardia, Keven Bluteau, Gabriel Lortie-Cloutier, Thien Duy Tran
<p>We explore the factor exposure heterogeneity in green and brown stocks using the peer-exposure ratio. By creating peer groups of S&P 500 index firms over 2014-2020 based on their greenhouse gas emission levels, we find that, on average, the largest factor exposure heterogeneities are observed for the value factor in green stocks and the momentum factor in brown stocks. Moreover, investing in brown stocks allows managers to distinguish themselves more in terms of factor exposure than green stocks, except in the value factor. Compared to earlier periods, investment managers now have more opportunities to differentiate themselves in their factor exposures.</p>
2023-02-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29872023-02-21T10:33:23-05:002023-02-21T10:34:15-05:00G-2023-01 : Mitigating equipment overloads due to electric vehicle charging using customer incentivesFeng Li, Ilhan Kocar, Antoine Lesage-Landry
<p>This paper first presents a time-series impact analysis of charging electric vehicles (EVs) to loading levels of power network equipment considering stochasticity in charging habits of EV owners. A novel incentive-based mitigation strategy is then designed to shift the EV charging from the peak hours when the equipment is overloaded to the off-peak hours and maintain equipment service lifetime. The incentive level and corresponding contributions from customers to alter their EV charging habits are determined by a search algorithm and a constrained optimization problem.
The strategy is illustrated on a modified version of the IEEE 8500 feeder with a high EV penetration to mitigate overloads on the substation transformer.</p>
2023-01-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29862023-02-21T09:44:26-05:002023-02-21T11:47:24-05:00G-2023-05 : Strong consistency and rate of convergence of switched least squares system identification for autonomous Markov jump linear systemsBorna Sayedana, Mohammad Afshari, Peter E. Caines, Aditya Mahajan
<p>Dans cet article, nous étudions le problème de l'identification de système pour les systèmes linéaires à saut de Markov autonomes (MJS) avec des observations d'état complètes.
Nous proposons la méthode des moindres carrés commutés pour l'identification de MJS, montrons que cette méthode est fortement cohérente et dérivons des taux de convergence dépendants et indépendants des données.
En particulier, notre taux de convergence indépendant des données montre que, presque sûrement, l'erreur d'identification du système est <code>\({\mathcal O}\big(\sqrt{\log(T)/T} \big)\)</code> où <code>\(T\)</code> est l'horizon temporel. Ces résultats montrent que la méthode des moindres carrés commutés pour MJS a le même taux de convergence que la méthode des moindres carrés pour les systèmes linéaires autonomes.
Nous dérivons nos résultats en imposant une hypothèse générale de stabilité au modèle appelée stabilité au sens moyen. Nous montrons que la stabilité au sens moyen est une forme de stabilité plus faible par rapport aux hypothèses de stabilité couramment imposées dans la littérature. Nous présentons des exemples numériques pour illustrer les performances de la méthode proposée.</p>
2023-02-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29842023-02-17T11:08:56-05:002023-02-17T11:18:45-05:00G-2022-50 : \(\texttt{Krylov.jl}\): A Julia basket of hand-picked Krylov methodsAlexis Montoison, Dominique Orban
<p>Cet article présente <code>\(\texttt{Krylov.jl}\)</code>, un module Julia qui contient une collection de processus et méthodes de Krylov pour résoudre une variété de problèmes linéaires.</p>
2022-11-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29852023-02-20T15:12:06-05:002023-02-20T15:12:06-05:00G-2023-02 : A dedicated pricing algorithm to solve a large family of nurse scheduling problems with branch-and-priceAntoine Legrain, Jérémy Omer
<p>In this paper, we describe a branch-and-price algorithm for the personalized nurse scheduling problem.
The variants that appear in the literature involve a large number of constraints that can be hard or soft, meaning that they can be violated at the price of a penalty.
We capture the diversity of the constraints on individual schedules by seven generic constraints characterized by lower and upper bounds on a given quantity.
The core of the column generation procedure is in the identification of indivual schedules with minimum reduced cost.
For this we solve a shortest path problem with resource constraints (SPPRC) where several generic constraints are modeled as resource constraints.
We then describe dominance rules adapted to the presence of both upper and lower bounds on the resources and leverage soft constraints to improve the dominance.
We also describe several acceleration techniques for the solution of the SPPRC, and branching rules that fit the specificities of the problem.
Our numerical experiments are based on the instances of three benchmarks of the literature including those of the two international nurse rostering competitions (INRC-I and INRC-II).
Their objective is three-fold: assess the dominance rules and the acceleration techniques, investigate the capacity of the algorithm to find provable optimal solutions of instances that are still open, and conduct a comparison to best published results.
The most noticeable conclusion is that the improved solution of the SPPRC allows to solve optimally all the INRC-II instances where a 4-weeks planning horizon is considered and 40% of the 8-weeks instances.</p>
2023-01-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29752022-10-24T14:43:55-04:002023-01-24T13:58:02-05:00G-2022-45 : Rapid method for impact analysis of grid-edge technologies on power distribution networksFeng Li, Ilhan Kocar, Antoine Lesage-Landry
<p>This paper presents a novel rapid estimation method (REM) to perform stochastic impact analysis of grid-edge technologies (GETs) to the power distribution networks. The evolution of network states' probability density functions (PDFs) in terms of GET penetration levels are characterized by the Fokker-Planck equation (FPE). The FPE is numerically solved to compute the PDFs of network states, and a calibration process is also proposed such that the accuracy of the REM is maintained for large-scale distribution networks.
The approach is illustrated on a large-scale realistic distribution network using a modified version of the IEEE 8500 feeder, where electric vehicles (EVs) or photovoltaic systems (PVs) are installed at various penetration rates.
It is demonstrated from quantitative analyses that the results from our proposed approach have negligible errors comparing with those obtained from Monte Carlo simulations. </p>
2022-10-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/28562021-05-13T13:30:06-04:002023-01-30T13:48:12-05:00G-2021-11 : Quasi-maximum likelihood for estimating structural models Malek Ben-Abdellatif, Hatem Ben-Ameur, Rim Chérif, Tarek Fakhfakh
<p>The estimation of the structural model poses a major challenge as its
underlying asset (the firm's asset value) is not directly observable. We
extend the maximum likelihood (ML) method of Duan (1994 and 2000), and
propose a quasi-maximum likelihood (QML) approach that remains appropriate
under alternative Markov assumptions, arbitrary debt payment schedules, and
extended balance sheets. QML alternates between dynamic programming and
maximum likelihood to simultaneously solve and estimate general structural
settings. QML is highly flexible and effective. To support our construction,
we conduct a numerical investigation and show that ML and QML agree in
Merton's (1974) setting. Then, we achieve an empirical investigation,
spotlight the credit-spread puzzle, and discuss a partial remedy via jumps
and bankruptcy costs.</p>
2021-03-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29912023-03-28T16:27:53-04:002023-03-28T16:28:25-04:00G-2022-59 : Offline-online retail collaboration via pickup partnershipZahra Jalali, Maxime Cohen, Necati Ertekin, Mehmet Gumus
<p>Summary: We study an increasingly popular retail practice called pickup partnership that allows
online retailers to offer an in-store pickup service by partnering with a physical store. In practice,
online retailers use two policies for such partnerships:</p>
<p>-Fixed fee policy: Under this policy, online partner signs a partnership with a physical
store and pays a fixed fee to the partner so that the customers can visit the offline store
to pick up their orders.</p>
<p>-Coupon policy: Under this policy, online partner issues a coupon (discount or promotion
coupon) to the customers. When the customers visit the offline store to pick up their
orders, they use the coupon to purchase additional items from the offline store.
These policies have pros and cons. Our research found that the fixed fee policy is very easy to
implement whereas coupon policy generates cross-selling opportunity for the offline partner.</p>
2022-12-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29902023-03-28T16:23:40-04:002023-03-28T16:23:40-04:00G-2022-57 : Optimal multi-robot formations for relative pose estimation using range measurementsCharles Champagne Cossette, Mohammed Shalaby, David Saussié, Jérôme Le Ny, James Richard Forbes
<p>In multi-robot missions, relative position and attitude information between robots is valuable for a variety of tasks such as mapping, planning, and formation control. In this paper, the problem of estimating relative poses from a set of inter-robot range measurements is investigated. Specifically, it is shown that the estimation accuracy is highly dependent on the true relative poses themselves, which prompts the desire to find multi-robot formations that provide the best estimation performance. By direct maximization of Fischer information, it is shown in simulation and experiment that large improvements in estimation accuracy can be obtained by optimizing the formation geometry of a team of robots. </p>
2022-12-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29892023-03-28T16:20:16-04:002023-03-28T16:20:16-04:00G-2022-55 : Addressing the cold start problem in privacy preserving content-based recommender systems using hypercube graphsNoa Tuval, Alain Hertz, Tsvika Kuflik
<p>Recommender systems provide recommendations to their users for items and services by creating a model tailored to each user to infer their preferences based on previous interactions they have made with the system, as well as possibly using additional information sources. The initial interaction of a user with a recommender system is problematic because, in such a so-called cold start situation, the recommender system has very little information about the user, if any. Moreover, in collaborative filtering, users need to share their preferences with the service provider by rating items while in content-based filtering there is no need for such information sharing. Graph-based user modeling has now become common practice and we have recently shown that a content-based model that uses hypercube graphs can determine user preferences with a very limited number of ratings while better preserving user privacy. In this paper, we confirm these findings on the basis of larger scale experiments.<br>
We thus address the cold start problem by building user models based on a small number of ratings. We also show that the proposed method outperforms standard machine learning algorithms when the number of available ratings is very limited.</p>
2022-12-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29882023-03-28T16:12:45-04:002023-03-28T16:13:03-04:00G-2022-54 : Incremental LNS framework for integrated production, inventory, and vessel scheduling: Application to a global supply chainEl Mehdi Er Raqabi, Ilyas Himmich, Nizar El Hachemi, Issmail El Hallaoui, François Soumis
<p>This paper presents a multiobjective, mixed-integer linear programming (MILP) model that integrates production scheduling, inventory management, and vessel assignment for a global supply chain. Given that such large-scale problems are NP-hard and usually suffer from symmetry, we conduct an exploratory analysis to identify complexity sources. Following this, we design a novel variant of the large neighborhood search metaheuristic to tackle the problem efficiently. While symmetry is considered an issue in the literature, the implemented algorithm provides a practical way of profiting from instead of breaking it. Computationally, we reach near-optimal solutions in real-world instances. Compared to the default CPLEX and a reference algorithm that mimics real life, we gain significantly in terms of time, quality, and the number of feasible integer solutions found during the solving process. In addition to efficiency, integrated optimization enhances operations management capabilities and supply chain resilience. </p>
2022-12-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29832023-01-24T14:14:40-05:002023-01-24T14:14:54-05:00G-2022-53 : MPILS: An automatic tuner for MILP solversIlyas Himmich, El Mehdi Er Raqabi, Nizar El Hachemi, Issmail El Hallaoui, Abdelmoutalib Metrane, François Soumis
<p>The parameter configuration problem consists of finding a parameter configuration that provides the most effective performance by a given algorithm. This paper addresses this problem for MILP solvers through a new multi-phase tuner based on the iterated local search metaheuristic. The goal is to find near-optimal, if not optimal, configuration(s) for efficiently solving large-scale industrial optimization problems. Instead of tuning in the entire configuration space induced by the set of parameters, the proposed tuner focuses on a small pool of parameters that is enhanced dynamically with new promising ones. Furthermore, it uses statistical learning to benefit from the dynamically accumulated information to forbid less promising parameter combinations. A computational study on a widely used commercial CPLEX solver with instances from the MIPLIB library and a real large-scale optimization problem highlights the promising potential of the tuner.</p>
2022-12-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29822023-01-24T14:06:45-05:002023-01-24T14:06:45-05:00G-2022-52 : A survey on AI-based scheduling models, optimization and prediction for hydropower generation: Variants, challenges, and future directionsYoan Villeneuve, Sara Séguin, Abdellah Chehri
<p>The most common form of renewable energy production around the world is hydropower. As a result of the growing demand for robust and environmentally friendly methods of energy generation around the world, it is imperative to develop and improve the current energy production processes. Machine learning has significantly contributed to numerous academic domains in the past decade, and hydropower is no exception. All three horizons of hydropower models, short-term, medium-term, and long-term, could benefit from machine learning. Currently, the majority of hydropower scheduling models employ dynamic programming. As a result of machine learning's use of a new evolution of pre-existing methodologies, unconstrained optimization also enables improvement. In this research paper, we review the current state of the hydropower scheduling problem and the development of machine learning as a type of optimization problem and prediction tool. In addition, the paper investigates the other conceivable roles that machine learning has taken on in recent years. To the best of our knowledge, this is the first survey article that provides a comprehensive overview of machine learning and artificial intelligence application in the hydroelectric power industry for Scheduling, Optimization, and Prediction.</p>
2022-12-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29812022-12-21T10:43:21-05:002022-12-21T10:50:20-05:00G-2022-56 : Erratum, counterexample and an additional revealing poll step for a result of ``Analysis of direct searches for discontinuous functions''Charles Audet, Pierre-Yves Bouchet, Loïc Bourdin
<p>Cette note fournit un contre-exemple à un théorème proposé dans la dernière partie de l'article <em>Analysis of direct searches for discontinuous functions</em>, Mathematical Programming Vol. 133, pp. 299-325, 2012.
Le contre-exemple repose sur une fonction-objectif <code>\(f:{\mathbb{R}}\to{\mathbb{R}}\)</code> qui satisfait toutes les hypothèses requises par le théorème mais contredit certaines de ses conclusions.
Un corollaire au théorème est également affecté par le contre-exemple.
Le principal problème révélé par le contre-exemple est la possibilité qu'une méthode de recherche directe (dDSM) génère une suite d'optimiseurs <code>\((x_k)_k\)</code> convergeant vers un point <code>\(x_*\)</code> en lequel <code>\(f\)</code> est discontinue et telle que la valeur-objectif <code>\(f(x_*)\)</code> est strictement inférieure à <code>\(\lim_{k\to\infty}f(x_k)\)</code>.
De plus, la dDSM ne génère aucun point dans l'une des deux branches de <code>\(f\)</code> au voisinage de <code>\(x_*\)</code>.
Cette note étudie également la preuve du théorème pour révéler des affirmations incorrectes dans l'article initial.
Enfin, ce travail propose une modifiation de la dDSM permettant d'obtenir les propriétés cassées par le contre-exemple.</p>
2022-12-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29802022-12-21T10:32:05-05:002022-12-21T10:32:05-05:00G-2022-51 : Inventory control and learning for one-warehouse multi-store system with censored demandRecep Bekci, Mehmet Gumus, Sentao Miao
<p>Motivated by our collaboration with one of the largest fast-fashion retailers in Europe, we study a two-echelon inventory control problem called the One-Warehouse Multi-Store (OWMS) problem when the demand distribution is unknown. This system has a central warehouse that receives an initial replenishment and distributes its inventory to multiple stores in each time period during a finite horizon. The goal is to minimize the total expected cost which consists of shipment costs, holding costs, lost-sales costs, and end-of-horizon disposal costs. The OWMS system is ubiquitous in supply chain management, yet its optimal policy is notoriously difficult to calculate even under the complete demand distribution case. In this work, we consider the OWMS problem when the demand is <em>censored</em> and its distribution is unknown <em>a priori</em>. The main challenge under the censored demand case is the difficulty in generating unbiased demand estimation. In order to address this, we propose a primal-dual algorithm in which we continuously learn the demand and make inventory control decisions on the fly. Results show that our approach has great theoretical and empirical performances.</p>
2022-11-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29792022-12-21T10:26:22-05:002022-12-21T10:26:22-05:00G-2022-49 : Online Newton's method with linear time-varying equality constraintsJean-Luc Lupien, Antoine Lesage-Landry
<p>We consider online optimization problems with time-varying linear equality constraints. In this framework, an agent makes sequential decisions using only prior information. At every round, the agent suffers an environment-determined loss and must satisfy time-varying constraints. Both the loss functions and the constraints can be chosen adversarially. We propose the Online Projected Equality-constrained Newton Method (OPEN-M) to tackle this family of problems. We obtain sublinear dynamic regret and constraint violation bounds for OPEN-M under mild conditions. Namely, smoothness of the loss function and boundedness of the inverse Hessian at the optimum are required, but not convexity. Finally, we show OPEN-M outperforms state-of-the-art online constrained optimization algorithms in a numerical network flow application.</p>
2022-11-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29782022-12-21T10:20:19-05:002023-01-23T10:10:42-05:00G-2022-48 : Short-term hydropower optimization in the day-ahead market using a nonlinear stochastic programming modelMohammad Jafari Aminabadi, Sara Séguin, Issouf Fofana, Stein-Erik Fleten, Ellen Krohn Aasgård
<p>Hydropower producers participate in the electricity market by providing bids in the day-ahead market auctions. Making good bids that obey all market rules and consider uncertain prices for large, interconnected hydropower watercourses is challenging. This investigation aims to find bidding strategies that attend to the market aspects and all constraints relevant to short-term hydropower production. This paper presents a stochastic mixed-integer nonlinear model and a nonlinear heuristic method for the bidding optimization problem and shows a comparison of the model's performance in two case studies. The comparison of the two models shows that their results are close and that the heuristic method can reach the optimal solution after a few iterations. The numerical experiments are also compared with results from the Short-term Hydro Optimization Program (SHOP), which is a software used for operational planning in the Nordic electricity market.</p>
2022-11-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29772022-12-21T10:15:51-05:002022-12-21T10:16:09-05:00G-2022-47 : Quantifying the impact of scenario tree generation methods on the solution of the short-term hydroscheduling problemMaissa Daadaa, Sara Séguin, Miguel F. Anjos, Kenjy Demeester
<p>This paper studies the properties of a stochastic optimization model for the short-term hydropower generation problem with uncertain inflows. The uncertainty is represented using scenario trees. Backward reduction and neural gas methods are used to generate and reduce a full scenario tree. The objective of this work is to evaluate the impact of scenario tree generation methods on the solution of the optimization. First, statistical tests are done where the expected volume, the variance and the standard deviation of each scenario tree are calculated and compared. Second, operational tests are realized, where the scenario trees are used as input to the stochastic programming model and the value of the objective function and solution are evaluated and compared. The model are tested on a 14 forecasted days and for a 10 days rolling-horizon for two powerhouses with five turbines each located in the Saguenay-Lac-St-Jean region of the province of Quebec in Canada.</p>
2022-11-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/29402022-04-22T18:20:46-04:002023-02-07T10:52:48-05:00G-2022-09 : Optimally scheduling public safety power shutoffsAntoine Lesage-Landry, Félix Pellerin, Joshua A. Taylor, Duncan Callaway
<p>In an effort to reduce power system-caused wildfires, utilities carry out public safety power shutoffs (PSPS) in which portions of the grid are de-energized to mitigate the risk of ignition. The decision to call a PSPS must balance reducing ignition risks and the negative impact of service interruptions. In this work, we consider three PSPS scheduling scenarios, which we model as dynamic programs.
In the first two scenarios, we assume that <code>\(N\)</code> PSPSs are budgeted as part of the investment strategy. In the first scenario, a penalty is incurred for each PSPS declared past the <code>\(N^\text{th}\)</code> event. In the second, we assume that some costs can be recovered if the number of PSPSs is below <code>\(N\)</code> while still being subject to a penalty if above <code>\(N\)</code>. In the third, the system operator wants to minimize the number of PSPS such that the total expected cost is below a threshold. We provide optimal or asymptotically optimal policies for each case, the first two of which have closed-form expressions. Lastly, we establish the applicability of the first PSPS model's policy to critical-peak pricing, and obtain an optimal scheduling policy to reduce the peak demand based on weather observations.</p>
2022-03-01GERADinfo@gerad.ca