2022 Optimization Days

HEC Montréal, Québec, Canada, 16 — 18 May 2022

Schedule Authors My Schedule

WA3 - Constraint Programming: Applications

May 18, 2022 10:30 AM – 12:10 PM

Location: Procter & Gamble (green)

Chaired by Gilles Pesant

4 Presentations

  • 10:30 AM - 10:55 AM

    A Constraint Programming model with the confidence constraint for robust short-term underground mine planning

    • Younes Aalian, presenter, Polytechnique Montréal
    • Michel Gamache, Polytechnique Montréal
    • Gilles Pesant, Polytechnique Montréal

    The short-term scheduling of activities in underground mines is an important step in mining operations. This procedure is a challenging optimization problem since it deals with many resources and activities conducted in a confined working space. Moreover, underground mining operations deal with numerous uncertainties such as the variability in the duration of activities. Conventional approaches for mine planning do not consider uncertainty in the scheduling decisions and thus result in impractical solutions. In this paper, a Constraint Programming (CP) model is proposed for short-term planning in underground mines. The developed model takes into account the technical requirements of underground operations to build realistic mine schedules. Furthermore, a confidence constraint is introduced in the CP model to ensure that the task durations take sufficiently large values with a certain threshold probability. The model allows generating robust short-term mine schedules up to the given confidence threshold without overestimating the duration of tasks. The presented approach is implemented in real data sets of an underground gold mine in Canada.

  • 10:55 AM - 11:20 AM

    Robust short-term underground mining scheduling models using constraint programming in an uncertain environment

    • Jérémy André, presenter,
    • Michel Gamache, Polytechnique Montréal
    • Gilles Pesant, Polytechnique Montréal

    Underground mining is a highly uncertain environment where activities durations may be affected by multiple uncertainty sources. Thus, short-term planning, which aims to schedule activities allocating resources to tasks on a given time horizon, becomes necessary to manage complex operations. We present a robust short-term scheduling model using constraint programming to build good robust feasible solutions for both mining development and production. The robust stochastic short-term model is based on multiple scenarios to produce a set of ordered robust sequences of activities for each disjunctive resource, minimizing the expected makespan.

    Then, the produced set of ordered sequences of activities for each resource is provided to a simulation model to evaluate performances of the set of robust sequences on new simulated data. Both models handle uncertainties about the duration of activities and resource breakdowns to produce more relevant solutions while taking into account various operational constraints.

    Implemented models are tested on real data sets from a sub-level long-hole stoping mine in Canada. Deterministic models have also been implemented to compare results with the robust approach but these models are often too optimistic. The constraint programming paradigm has been proven to be efficient to solve scheduling problems with scarce disjunctive resources.

  • 11:20 AM - 11:45 AM

    Hospital Optimizer: A Constraint Programming Based Software to Optimize Operating Rooms Schedule

    • Pankaj K. Singh, presenter, Université Laval
    • Nicolas Blais, Université Laval
    • Vanessa Simard, NQB.ai
    • Daniel Lafond, Thales Canada
    • Claude-Guy Quimper, Université Laval

    Operating room (OR) scheduling enables hospitals to improve quality of service and achieve high efficiency. Due to limited availability of specialty OR, specialist surgeons and various other constraints, scheduling of OR can become challenging, especially when scheduling period may range from two weeks to thirteen weeks. Matter is further complicated by the conflicting needs like, OR availability for emergency surgery and changing availability of surgeons while trying to keep a weekly schedule similar to the previous week’s schedule.

    We present the Hospital Optimizer, an application developed in collaboration with Thales Canada, using a two-stage Constraint Programming (CP) based approach that solves the OR scheduling problem in a specialty hospital. The first stage creates a schedule and the second stage improves it using a Large Neighbourhood Search (LNS). The objective is to keep the schedule of any two given weeks as similar as possible.

    We have tested our model on multiple types of demand data and compared their results of different LNS strategies visually. Our model was used to create a demonstration schedule for a real hospital.

  • 11:45 AM - 12:10 PM

    Enumerating Optimal Solutions in Kidney Exchange Programs

    • Behrouz Babaki, presenter, Wise Systems
    • Margarida Carvalho, Université de Montréal
    • Golnoosh Farnadi, HEC Montréal, Mila
    • William St-Arnaud, Université de Montréal

    Kidney exchange programs (KEPs) seek to match incompatible patient-donor pairs together, usually with the objective of maximizing the total number of kidney transplants. KEPs often have several optimal solutions. Since selecting one optimal solution translates to a decision on who receives a transplant, it has a major effect on the lives of patients. The current practice in selecting an optimal solution does not necessarily ensure fairness in the selection process. A possible way to address this issue is to enumerate all optimal solutions and select one of them using a randomized policy such that the patients' equity of opportunity to receive a transplant is promoted. This approach gives rise to the problem of enumerating all optimal solutions, which we tackle using a hybrid of constraint programming and linear programming.