Journées de l'optimisation 2014
Incluant une Journée industrielle de l'optimisation
HEC Montréal, 5  7 mai 2014
JOPT2014
HEC Montréal, 5 — 7 mai 2014
TB6 Programmation linéaire / Linear Programming
6 mai 2014 10h30 – 12h10
Salle: StHubert
4 présentations

10h30  10h55
Deploying Concavity Cuts in BILD Problems
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 pseudovertices. This strategies can overcome some literature results. Numerical experiments are presented.

10h55  11h20
DualGuided Pivot Rules for Linear Programming
We describe a generic primal algorithm guided by dual feasibility considerations. Special cases are the Primal Simplex, the strongly polynomial Minimum Mean CycleCanceling 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
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
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.