Optimization Days 2014

                                      Including an Industrial Optimization Day

                                             HEC Montréal, May 5 - 7, 2014

JOPT2014

HEC Montréal, 5 — 7 May 2014

Schedule Authors My Schedule

MD8 Programmation par contraintes 2 / Constraint Programming 2

May 5, 2014 03:30 PM – 05:10 PM

Location: TD Assurance Meloche Monnex

Chaired by Louis-Martin Rousseau

3 Presentations

  • 03:30 PM - 03:55 PM

    Constraint Programming for LNG Ship Scheduling and Inventory Management

    • Vikas Goel, ExxonMobil
    • Marla Slusky, Carnegie Mellon University
    • Willem-Jan van Hoeve, presenter, 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.

  • 03:55 PM - 04:20 PM

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

    • Amira Dems, presenter, 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.

  • 04:20 PM - 04:45 PM

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

    • Seyed Hossein Hashemi Doulabi, presenter, 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.

Back