4 Presentations

• 
  10:30 AM - 10:55 AM

  Deploying Concavity Cuts in BILD Problems

  • Maikel Geagea, presenter, 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.

• 
  10:55 AM - 11:20 AM

  Dual-Guided Pivot Rules for Linear Programming

  • Jacques Desrosiers, presenter, 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.

• 
  11:20 AM - 11:45 AM

  Improving the Quality of Dual Solutions in Column Generation

  • Hocine Bouarab, presenter, 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.

• 
  11:45 AM - 12:10 PM

  Uncertain Relative Efficiency Computation through Linear Programming

  • Vahid Partovi Nia, presenter, 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.