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

G-99-34

Column/Row Generation and Elimination Methods

, et

We study the solution of combinatorial problems with the column generation techniques when there is a very large number of both variables and constraints. We explore strategies which aims at combining generation and elimination procedures of both rows and columns, while providing a guarantee to reach the optimal solution. We illustrate those strategies on the channel assignment problem and we provide computational experience on some data provided by Bell Mobility for two urban cellular networks.

, 23 pages