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

TB6 Programmation linéaire / Linear Programming

6 mai 2014 10h30 – 12h10

Salle: St-Hubert

4 présentations

  • 10h30 - 10h55

    Deploying Concavity Cuts in BILD Problems

    • Maikel Geagea, prés., Polytechnique Montréal

    In the context of concave minimization, we propose two ways to extend the standard concavity cuts algorithm. First, we devise a strategy to dynamically update the cuts. Second, we allow cuts to be rooted at pseudo-vertices. This strategies can overcome some literature results. Numerical experiments are presented.

  • 10h55 - 11h20

    Dual-Guided Pivot Rules for Linear Programming

    • Jacques Desrosiers, prés., HEC Montréal
    • Jean-Bertrand Gauthier, GERAD - HEC Montréal
    • Marco E. Luebbecke, Aachen University

    We describe a generic primal algorithm guided by dual feasibility considerations. Special cases are the Primal Simplex, the strongly polynomial Minimum Mean Cycle-Canceling algorithm for network flow problems, and the Improved Primal Simplex. Properties of this generic algorithm allow identifying subsets of fixed dual variables that totally avoid degenerate pivots.

  • 11h20 - 11h45

    Improving the Quality of Dual Solutions in Column Generation

    • Hocine Bouarab, prés., Polytechnique Montréal
    • Francois Soumis, GERAD et Polytechnique
    • Issmail El Hallaoui, GERAD, Polytechnique Montréal
    • Abdelmoutalib Metrane, Polytechnique Montréal

    A degenerate master problem(MP) produces poor quality dual solutions increasing drastically the number of column generation(CG) iterations. We propose a new CG algorithm where, at each iteration, the dual solution is partially given by an aggregated MP and completed by an auxiliary problem. This approach produces more central dual solutions and the iterations number is considerably reduced. We report numerical results on instances of the Vehicle and Crew Scheduling Problem.

  • 11h45 - 12h10

    Uncertain Relative Efficiency Computation through Linear Programming

    • Vahid Partovi Nia, prés., Polytechnique Montréal

    Computing or predicting the relative efficiency of decision making units is one of the most important issues in management and resource allocation. Relative efficiency is easy to compute if there is just one output variable and one input variable. The ratio of the output divided by the input is the efficiency, and the computed efficiencies are scaled to have maximum unit value to produce the relative efficiency. While there are several output and input variables , the relative efficiency computation is generalized by means of linear programming, also called Data Envelopment Analysis. However, often input and output measurements include uncertain measurements, and this complicates the analysis further. I will talk about the proper handling of this uncertainty in computation of the relative efficiency.