Jean Bertrand Gauthier
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Jean Bertrand Gauthier has a total of 6 co-authors. Here are the top co-authors by number of shared publications:
- Jacques Desrosiers
HEC Montréal and GERAD, Montréal, Canada H3T 2A7
5 shared publications - Marco E. Lübbecke
Chair of Operations Research, RWTH Aachen University, Aachen, Germany
4 shared publications - Antoine Legrain
Polytechnique Montreal
1 shared publication - Guy Desaulniers
Department of Mathematics and Industrial Engineering, Polytechnique Montréal, Montréal, Canada
1 shared publication Hocine Bouarab
Polytech Montreal, Montreal, PQ H3C 3A7, Canada
1 shared publicationJacques Desrosiers
1 shared publication
Latest Publications
- 1 April 2022
- Published by Elsevier in European Journal of Operational Research
- Vol. 298 (1) , 36-44
The minimum mean cycle-canceling algorithm for linear programs
- 1 April 2022
- Published by Elsevier in European Journal of Operational Research
- Vol. 298 (1) , 36-44
The minimum mean cycle-canceling algorithm for linear programs
- 1 October 2018
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 66 (5) , 1376-1389
Vector Space Decomposition for Solving Large-Scale Linear Programs
We develop an algorithmic framework for linear programming guided by dual optimality considerations. The solution process moves from one feasible solution to the next according to an exchange mechanism that is defined by a direction and a resulting step size. Part of the direction is obtained via a pricing problem devised in primal and dual forms. From the dual perspective, one maximizes the minimum reduced cost that can be achieved from splitting the set of dual variables in two subsets: one being fixed while the other is optimized. From the primal perspective, this amounts to selecting a nonnegative combination of variables entering the basis. The direction is uniquely complemented by identifying the affected basic variables, if any. The framework is presented in a generic format motivated by and alluding to concepts from network flow problems. It specializes to a variety of algorithms, several of which are well known. The most prominent is the primal simplex algorithm where all dual variables are fixed: this results in the choice of a single entering variable commonly leading to degenerate pivots. At the other extreme, we find an algorithm for which all dual variables are optimized at every iteration. Somewhere in between these two extremes lies the improved primal simplex algorithm for which one fixes the dual variables associated with the nondegenerate basic variables and optimizes the remaining ones. The two last variants both bestow a pricing problem providing necessary and sufficient optimality conditions. As a result, directions yielding strictly positive step sizes at every iteration are also issued from these pricing steps. These directions move on the edges of the polyhedron for the latter while the former can also identify interior directions.
- 1 October 2018
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 66 (5) , 1376-1389
Vector Space Decomposition for Solving Large-Scale Linear Programs
We develop an algorithmic framework for linear programming guided by dual optimality considerations. The solution process moves from one feasible solution to the next according to an exchange mechanism that is defined by a direction and a resulting step size. Part of the direction is obtained via a pricing problem devised in primal and dual forms. From the dual perspective, one maximizes the minimum reduced cost that can be achieved from splitting the set of dual variables in two subsets: one being fixed while the other is optimized. From the primal perspective, this amounts to selecting a nonnegative combination of variables entering the basis. The direction is uniquely complemented by identifying the affected basic variables, if any. The framework is presented in a generic format motivated by and alluding to concepts from network flow problems. It specializes to a variety of algorithms, several of which are well known. The most prominent is the primal simplex algorithm where all dual variables are fixed: this results in the choice of a single entering variable commonly leading to degenerate pivots. At the other extreme, we find an algorithm for which all dual variables are optimized at every iteration. Somewhere in between these two extremes lies the improved primal simplex algorithm for which one fixes the dual variables associated with the nondegenerate basic variables and optimizes the remaining ones. The two last variants both bestow a pricing problem providing necessary and sufficient optimality conditions. As a result, directions yielding strictly positive step sizes at every iteration are also issued from these pricing steps. These directions move on the edges of the polyhedron for the latter while the former can also identify interior directions.
- 1 September 2017
- Published by Elsevier in Operations Research Letters
- Vol. 45 (5) , 503-507
Linear fractional approximations for master problems in column generation
- 1 September 2017
- Published by Elsevier in Operations Research Letters
- Vol. 45 (5) , 503-507
Linear fractional approximations for master problems in column generation
- 1 August 2017
- Published by Elsevier in Computers & Operations Research
- Vol. 84, 16-32
A strongly polynomial Contraction-Expansion algorithm for network flow problems
- 1 August 2017
- Published by Elsevier in Computers & Operations Research
- Vol. 84, 16-32
A strongly polynomial Contraction-Expansion algorithm for network flow problems
- Open Access
- 1 June 2016
- Published by Elsevier in EURO Journal on Transportation and Logistics
- Vol. 5 (2) , 161-204
Tools for primal degenerate linear programs: IPS, DCA, and PE
- 1 June 2016
- Published by Elsevier in EURO Journal on Transportation and Logistics
- Vol. 5 (2) , 161-204
Open AccessTools for primal degenerate linear programs: IPS, DCA, and PE
- 19 November 2015
- Published by Springer Nature in Constraints
- Vol. 21 (4) , 577-596
Operating room management under uncertainty
- 19 November 2015
- Published by Springer Nature in Constraints
- Vol. 21 (4) , 577-596
Operating room management under uncertainty
- 1 December 2014
- Published by Elsevier in Operations Research Letters
- Vol. 42 (8) , 553-557
Decomposition theorems for linear programs
- 1 December 2014
- Published by Elsevier in Operations Research Letters
- Vol. 42 (8) , 553-557
Decomposition theorems for linear programs