2018 Optimization Days

HEC Montréal, Québec, Canada, 7 — 9 May 2018

Schedule Authors My Schedule

WA5 Two-stage stochastic programming with chance constraints

May 9, 2018 10:30 AM – 12:10 PM

Location: Manuvie (54)

Chaired by Fabian Bastin

4 Presentations

  • 10:30 AM - 10:55 AM

    Stochastic lot-sizing problem with joint service level constraints

    • Narges Sereshti, presenter, HEC Montréal
    • Adulyasak Yossiri, HEC Montreal
    • Jans Raf, HEC Montréal

    In this research, the stochastic lot sizing problem for which the objective is to minimize the total cost whereas the decisions are subject to certain demand fulfillment criteria, is considered. These service levels are usually defined for each product. We investigate a joint service level which is defined jointly for multiple products in addition to individual service levels when uncertainty in the demand is present. Two different mathematical models are proposed to approximate this problem; the first one is based on probabilistic constraints and the second one is based on a scenario set.

  • 10:55 AM - 11:20 AM

    On a two-stage stochastic optimization problem with stochastic constraints and nested sampling

    • Thuy Anh Ta, presenter, Université de Montréal
    • Pierre L'Ecuyer, Université de Montréal
    • Fabian Bastin, Université de Montréal

    We consider a two-stage stochastic discrete program in which some of the second stage constraints have no closed form and need to be approximated by simulation (i.e., expected value constraints). We study the sample average approximation (SAA), which allows to approximate the solution to the two-stage problem. In particular, we study a nested sampling approach that includes the number of second stage scenarios and the number of replications per scenario to estimate the second stage constraint. We show that, in the second-stage problem, given a scenario, with probability one, optimal values and solutions to the SAA converge to those of the exact problem when the sample sizes go to infinity. However, in the two-stage problem, these convergence results of the second-stage problem do not hold uniformly for all scenarios. Despite of having this issue, we show that, with probability one, the optimal values and solutions given by the SAA approach converge to the true one with large enough sample sizes. We apply the SAA method to the staffing problem in call centers, i.e., the problem of how to optimize the numbers of multi-skill agents while satisfying some quality of service (QoS) constraints.
    The staffing allocation has to be decided under an uncertain arrival rate, but can be adjusted at some additional cost when the arrival rate is more precisely known. The results show the efficiency of the SAA approach with relatively large numbers of samples.

  • 11:20 AM - 11:45 AM

    A learning-based approach for multi-skill staffing optimization in call centers

    • Mai Anh Tien, presenter, Université de Montréal
    • Thuy Anh Ta, Université de Montréal
    • Fabian Bastin, Université de Montréal
    • Pierre L'Ecuyer, Université de Montréal

    We study a staffing problem in multi-skill call centers. The objective is to minimize the total cost of agents under some probability constraints defined over the randomness of the service level in a given time period. We formulate and solve a sample average approximation (SAA) version of the problem, where the probability functions in the constraints are expressed as functions of the staffing for a fixed sequence of random numbers driving the simulation. There are several challenges lying in solving this problem, namely, the non-linearity of the constraints, the noisiness of simulation, and the complication of large problem instances. We propose a nonlinear regression approach to approximate the probability functions, and design a learning-based algorithm to efficiently find staffing solutions. Our algorithm performs three steps in an iterative manner, namely, a simulation step to generate probability values given each staffing candidate, a learning step to learn the shape of the probability functions, and the third step concerns solving an integer linear program to obtain new staffing solutions. We test our algorithm with data sets collected from real-life call centers, and we show that our approach returns better solutions in shorter computational times, compared to existing approaches in the literature.

  • 11:45 AM - 12:10 PM

    A two-stage stochastic model for scheduling aircraft arrivals under uncertainty

    • Ahmed Khassiba, Université de Montréal
    • Fabian Bastin, presenter, Université de Montréal
    • Sonia Cafieri, ENAC
    • Bernard Gendron, Université de Montréal, CIRRELT
    • Marcel Mongeau, ENAC

    Efficient sequencing and scheduling aircraft arrivals up to a few hours before landing is foreseen to be a key measure towards limiting delays and mitigate air traffic growth. This yields greater uncertainty on predicted arrival times to be dealt with. To address this problem, we propose a two-stage stochastic optimization model enriched by chance constraints.

Back