Column-Generation in Integer Linear Programming
Programa de Engenharia de Sistemas e
Computação – COPPE – Universidade Federal do Rio de
Partially supported by CNPq, CAPES, FUJB, FAPERJ, PRONEX.
2 Departamento de Computación – Facultad de Ciencias Exactas y Naturales – Universidad de Buenos Aires, Argentina; firstname.lastname@example.org.. Partially supported by grants UBACYT EX036, CONICET 644/98.
We present an exact method for integer linear programming problems that combines branch and bound with column generation at each node of the search tree. For the case of models involving binary column vectors only, we propose the use of so-called geometrical cuts to be added to the subproblem in order to eliminate previously generated columns. This scheme could be applied to general integer problems without specific structure. We report computational results on a successful application of this approach to a telecommunications network planning problem.
Key words: Column-generation / integer programming / branch-and-price.
© EDP Sciences, 2003