Journées de l'optimisation 2014

                             Incluant une Journée industrielle de l'optimisation

                                              HEC Montréal, 5 - 7 mai 2014


HEC Montréal, 5 — 7 mai 2014

Horaire Auteurs Mon horaire

MD8 Programmation par contraintes 2 / Constraint Programming 2

5 mai 2014 15h30 – 17h10

Salle: TD Assurance Meloche Monnex

Présidée par Louis-Martin Rousseau

3 présentations

  • 15h30 - 15h55

    Constraint Programming for LNG Ship Scheduling and Inventory Management

    • Vikas Goel, ExxonMobil
    • Marla Slusky, Carnegie Mellon University
    • Willem-Jan van Hoeve, prés., Carnegie Mellon University
    • Kevin Furman, ExxonMobil
    • Yufen Shao, ExxonMobil

    We propose a constraint programming approach for the optimization of inventory routing in the liquefied natural gas industry. We present two constraint programming models that rely on a disjunctive scheduling representation of the problem. We also propose an iterative search heuristic to generate good feasible solutions for these models. Computational results on a set of large scale test instances demonstrate that our approach can find better solutions than existing approaches based on mixed integer programming, while being 4 to 10 times faster on average.

  • 15h55 - 16h20

    A Hybrid Constraint Programming Approach to a Wood Procurement Problem with Bucking Decision

    • Amira Dems, prés., Polytechnique Montreal
    • Jean-Marc Frayret, Polytechnique Montréal, CIRRELT
    • Louis-Martin Rousseau, Polytechnique Montréal

    We present a wood procurement problem that arises in the Eastern Canadian context.
    We will solve a multi-period wood supply planning problem, while taking into account bucking decisions.
    Furthermore, we present a form of flexibility which allows changing the harvesting capacity from time period to another.
    We study its impact upon the harvesting capacity used and the harvesting cost.
    We assessed its performance by comparing it to a variant where the harvesting capacity is kept unchanged.
    To address this problem, we develop a hybrid approach based on both Constraint and Mathematical Programming. In the first phase, we propose a constraint programming model dealing with forest sites harvesting and bucking problem. The result of this model will be used as an initial partial solution for the whole problem formulated as a mixed integer model.
    We tested the two versions of the problem on a set of different demand instances and we compared their results.

  • 16h20 - 16h45

    A General Model for Operating Room Planning and Scheduling Problems; a Constraint Programming-Based Branch-and-Price-and-Cut Approach

    • Seyed Hossein Hashemi Doulabi, prés., Polytechnique Montréal
    • Louis-Martin Rousseau, Polytechnique Montréal
    • Gilles Pesant, Polytechnique Montréal

    The goal of this paper is to present an efficient algorithm capable of solving a wide range of integrated operating room planning and scheduling problems which combine the assignment of surgeries to operating rooms and their scheduling over a short-term planning horizon. There are many details such as maximum daily working hours of surgeons, prevention from overlapping of surgeries corresponding to the same surgeon, obligatory cleanings due to switching from infectious to non-infectious surgeries and due dates of surgeries which must be respected. The problem is formulated as a mathematical programming model and a branch-and-price-and-cut algorithm is developed based on a constraint programming model to solve the subproblem. Some dominance rules and a fast infeasibility checking criterion based on a multidimensional knapsack problem are also developed which effectively improve the efficiency of the constraint programming model. Extensive computational results demonstrate the superiority of the proposed method to a compact mathematical formulation in the literature.