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

G-99-18

How to Combine a Column and Row Generation Method with a Column or Row Elimination Procedure - Application to a Channel Assignment Problem

, et

Solving exactly large instances of the channel assignment problem often requires to solve large linear programs with respect to the number of columns or rows. Considering the models proposed by Jaumard et al. (1998) which make use of column generation methods, it is necessary to combine those methods with some row generation procedures in order to handle the huge number of constraints. However, in order to keep a reasonable size of the linear programs, it is often interesting to eliminate some rows and columns from time to time. In this paper, we explore strategies which aims at combining column and row generation and elimination procedures, while providing a guarantee to reach the optimal solution. Computational experience are presented on some data provided by Bell Mobility for an urban cellular network.

, 25 pages