| Issue |
RAIRO-Oper. Res.
Volume 37, Number 2, April-June 2003
|
|
|---|---|---|
| Page(s) | 67 - 83 | |
| DOI | https://doi.org/10.1051/ro:2003014 | |
| Published online | 15 November 2003 | |
Column-Generation in Integer Linear Programming
1
Programa de Engenharia de Sistemas e
Computação – COPPE – Universidade Federal do Rio de
Janeiro, Brasil.
Partially supported by CNPq, CAPES, FUJB, FAPERJ, PRONEX.
2
Departamento de Computación – Facultad de
Ciencias Exactas y Naturales – Universidad de Buenos Aires,
Argentina; irene@dc.uba.ar.. Partially supported by grants
UBACYT EX036, CONICET 644/98.
Received:
January
2002
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
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.