Groupe d’études et de recherche en analyse des décisions

G-2015-82

A linear fractional pricing problem for solving linear programs

, et

This paper introduces a new primal algorithm for solving a linear program LP. In this algorithm, a pricing problem, namely a linear fractional program, is solved at each iteration to compute the largest possible minimum reduced cost over all variables. The linear version of this pricing problem obtained from the Charnes-Cooper transformation optimizes the dual vector under the constraint that the primal and dual objective values of LP must be equal. The solution of the pricing problem is used to update the current primal solution or to prove that it is optimal when the minimum reduced cost is null. The main properties of this algorithm are that, at every iteration except the last one, the cost of the primal solution decreases, the sum of the variables in the primal solution increases, and the minimum reduced cost also increases. We show that the minimum reduced cost converges to zero with a super-geometric growth rate.

, 20 pages