Stochastic Optimization

Contributed Session

Time Slot: Thursday Morning

Room: 001

Chair: Claudia Archetti

Multi-Stage Stochastic Optimization for a Biorefinery Supply Chain in Spain

Time: 9:00

Javier Faulin (Public University of Navarre), Serrano-Hernandez Adrian, Cadarso Luis, Ballano Aitor, Sawik Bartosz

Nowadays, biofuels are evolving as renewable and sustainable energy sources, especially on developed countries, due to the neutral CO2 emissions within their complete cycle. Regarding this topic, a biorefinery is considered to be set in Northern Spain. The problem considers uncertainty in biomass prices and availability, therefore, a stochastic optimization approach is needed to reduce the risks of the project. The optimization is represented as a three-stage scenario tree, composed of strategic and tactical nodes. The former refers to location of the biorefinery, while the latter refers to the rent of different warehouses. Additionally, operational nodes are rooted to the strategic and tactical nodes forming two-stage operational scenario trees. In these operational nodes, decisions related to the biomass acquisition are made.Meaningful insights are obtained from the application of stochastic optimization at all levels: strategic (the facility location problem), tactical (warehouses strategy) and operational (biomass purchases), highlighting a superior performance than the deterministic equivalent model.

Stochastic Dual Dynamic Programming and Lagrangian decomposition for seasonal storage valuation in SMS++

Time: 9:20

Antonio Frangioni (Dipartimento di Informatica, Università di Pisa), van Ackooij Wim, Lobato Rafael D.

The increase in the share of renewable energy sources in the power system,especially intermittent ones like solar and wind, brings several challenges. Asboth energy production and demand vary throughout the year (in winter, forexample, there is a reduction in the supply of solar energy while the demandfor energy for heating increases), energy storage becomes a relevant factor totake advantage of excess energy produced in certain seasons of the year andrespond to increased energy demand in others. An important system for seasonalstorage is that formed by cascading hydroelectric reservoirs. The managementof such systems is a challenging task which hinges on a good assessment ofthe future value of stored energy (water) in these systems. In order toassess the value of water, and thus be able to properly manage these reservoirsystems, a large-scale multi-stage stochastic problem spanning a year must besolved, where each stage is a weekly unit-commitment problems. Since theunit-commitment problems are non-convex in nature, they make the seasonalstorage valuation problem unsuitable for what would otherwise be the mostnatural approach to solve it, i.e., Stochastic Dual Dynamic Programming. Inthis work we exploit the natural convexification capabilities ofLagrangian relaxation to devise a Stochastic Dual Dynamic Programming approachto the seasonal storage valuation problem where the Lagrangian Dual of thesingle-stage subproblems is solved (using a Bundle-type approach), whichcorresponds to solving the convexified relaxation of the original problem.This is known to be at least as tight as, and typically strictly tighter than,the standard way to convexify a stochastic MINLP amenable to theStochastic Dual Dynamic Programming approach, i.e., the continuous relaxation.We report on extensive experiments which show that these huge-scalestochastic problems can indeed be solved on HPC architectures. This is madepossible by the use of the SMS++ software framework(https://smspp.gitlab.io/) for large-scale problems with multiple nestedforms of structure, and in particular by its native parallel capabilities thatallow to exploit two different forms of parallelization (between scenarios inthe SDDP approach and within subproblems in the Lagrangian one) at the sametime.

Robust Optimization for Smart Charging of Electrical Vehicles

Time: 9:40

Maxime Grangereau (EDF Lab Paris Saclay,), Laurent El Ghaoui, Fangda Gu,Riadh Zorgati

We present a robust optimization approach accounting for various uncertainties affecting Electrical Vehicles (EV) charging stations operations, such as electricity prices, vehicle arrival and departure times, and state of charge at arrival. We develop the robust counterparts for two smart charging models. The first model, based on aggregated demand, optimizes the charging profile over a time span when the aspect of the allocation of vehicles to the different charging outlets is ignored. When considering the problem of minimizing the charging price using a linear pricing model, charging occurs only at times with lower electricity prices and with high EV availability, whereas if we consider a quadratic cost functional, consumption is smoothed over the time horizon and can be obtained by the classical “water-filling” approach. We consider in this first model three sources of uncertainty: electricity prices, initial states of charge of vehicles when they arrive at the charging station and arrival/departure times of vehicles. We propose several robust counterparts of the optimal charging model with linear price accounting for these three sources of uncertainties. • The robust counterpart of the model accounting for price uncertainty is cast as a Second-Order Cone problem, for which numerical results show that its solution achieves a balance between the deterministic linear pricing model, where charging at low prices moments, and the “water-filling” solution, which dispatches consumption uniformly over time. • While the robust counterpart of the model accounting for uncertainties in the initial states of charge of vehicles may lead to overly conservative results, an affinely adjustable robust counterpart can be cast as a linear programming problem and strikes a good balance between conservativeness, computation time and performance. • We use scenario uncertainty to account for the random arrival/departure times. Naïve use of this approach may lead to overly conservative results as one needs to provision for every possible scenario. An approach called interval uncertainty, which assumes independence of the uncertainty impacting different vehicles allows to reduce the number of scenarios to consider. An affinely adjustable robust counterpart model allows to reach good performance and can be cast as a linear programming problem of moderate size if one considers interval uncertainty and a finite number of scenarios. The second model, involving the allocation of EVs to the different charging station’s sockets, trades-off profit versus a measure of customer satisfaction. We develop a scenario-based robust counterpart of this model where each arrival and departure times corresponds to a scenario, assuming that the initial state of charge of each EV is fully known. We also suggest another formulation of this problem, based on the cardinality function, which may be more convenient when dealing with uncertainties. In this model, physical limits on charging and load constraints are convex while vehicle and socket assignments constraints, re-formulated by using the cardinality (total number of non-zero components), require some vector to be of cardinality one, which lead to nonconvex constraints. Assuming a linear objective, our problem can be expressed as a linear programming problem with cardinality constraints. We review the use of some efficient heuristics to deal with cardinality constraints, such as L1-norm approximations or an entropy function approach.

Robust optimization models in call centers workforce management

Time: 10:00

Stefano Smriglio (DISIM – Università degli Studi dell’Aquila), Mattia Sara, Rossi Fabrizio

Workforce management (WFM) is a complex process and represents aprominent issue in cal
l centers optimization. Its general goal is tofind a satisfactory trade-off between the Level of Service (LoS)provided to customers and personnel costs. LoS is mostly based onwaiting times and quality of the response, while personnel costsconstitute one major expense for call center companies.WFM is traditionally split into a sequence of almost separate steps: forecasting call volumes(forecasting); determining the staffing levels, defined as the numberof agents required at each time period to guarantee the desired LoS(staffing); translating them into agents work shifts (shiftscheduling); assigning agents to such shifts (rostering) and, finally,monitoring out-of-adherence situations at operational level andreacting accordingly. This process offers several significantchallenges for stochastic modelling and has been deeply investagated bythe scientific literature. In particular, such adecomposition is well-known to be highly suboptimal for severalpractical reasons. For instance, the staffing levels are hard to coverwith shifts, leading to considerable overstaffing. Moreover, workshifts include rest breaks which may impact significantly on the LoS.We present two robust optimization models where agents flexibility isexploited so as to handle such drawbacks. In one case, we propose atwo-stage robust model aimed at integrating staffing with shiftscheduling with the goal of preserving LoS from unpredicted demandfluctuations. As for workbreak scheduling, we introduce an element which isrelevant in practice but hardly studied scientifically: the agentssatisfaction. Again, We illustrate a two-stage robust optimization model forshift scheduling, where agents are free to decide when to have breakswithin the regulatory restrictions. Practical cases are discussed,showing the trade off between industrial costs and agents autonomy.

Reinforcement Learning Approaches for the Orienteering Problem with Stochastic and Dynamic Release Dates

Time: 10:20

Claudia Archetti (ESSEC Business School), Li Yuanyuan, Ljubic Ivana

E-commerce markets are booming at remarkable rates. Due to an unprecedented series of lockdowns, billions of people stay at home to prevent the spread of the virus. It is reported that the e-commerce revenue saw a 10% increase in Europe in 2020 due to the pandemic. At the same time, the expectations of customers in terms of service quality are also increasing. When it comes to the specific challenges to improve customers’ satisfactions on delivery, one of the crucial features is related to the starting point of the last-mile delivery leg. An important feature of last-mile distribution is that its operations start as soon as parcels are delivered to the final logistic center, typically a city distribution center (CDC). Given the short delivery times requested by the customers, delivery operations typically need to start before all parcels expected to arrive that day are available at the CDC. This raises a question: whether to wait for more or all parcels to be delivered at the CDC or to start the delivery as soon as there is any available parcel and vehicle?In this paper, we focus on the sequential decision making problem related to when to deliver parcels and which parcels to deliver under the assumption that the time at which parcels become available at the CDC (called release dates) is stochastic and dynamic. We introduce a new problem called the Orienteering Problem with Stochastic and Dynamic Release Dates (DOP-rd) where a single and uncapacitated vehicle is serving customer requests with no time window, and the service has to finish within a deadline. The release dates are considered to be uncertain, stochastically and dynamically updated during the sequential decision making process. The objective is to maximize the number of requests served within the deadline.We model the problem as a Markov decision process and present two approximation approaches for its solutions. Both are based on scenario generations representing realizations of RDs and make use of a batch approach to approximate the value of future information, and specifically to approximate the number of requests served in future routes, i.e., routes that leave the depot in a future time instant. The two approximation approaches we propose are: Policy Function Approximation (PFA) through a consensus function in which a ILP determines, for each scenario, the requests to serve immediately, i.e., in a route leaving the depot immediately, and those included in future routes, and a consensus function over all scenarios determines the final solution; one-step look-ahead policy with Value Function Approximation (VFA) where a two-stage stochastic model is solved in which the first stage is to determine the route leaving immediately, while the second stage concerns future routes. We perform computational tests on a set of benchmark instances. We compare the two approaches described above with myopic approaches mimicking common practice and upper bounds related to perfect information. The results show that both PFA and VFA largely outperform myopic approaches and provide reasonable gaps with respect to the solution with perfect information.