Geodesic
Column-generation in integer linear programming
Maculan, Nelson  ; Passini, Marcos de Mendonça ; Brito, José André de Moura ; Loiseau, Irene1 
1 Departamento de Computación – Facultad de Ciencias Exactas y Naturales – Universidad de Buenos Aires, Argentina; Partially supported by grants UBACYT EX036, CONICET 644/98.
RAIRO - Operations Research - Recherche Opérationnelle, Tome 37 (2003) no. 2, pp. 67-83

Voir la notice de l'article provenant de la source Numdam

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.

DOI : 10.1051/ro:2003014
Keywords: column-generation, integer programming, branch-and-price

Maculan, Nelson  ; Passini, Marcos de Mendonça  ; Brito, José André de Moura  ; Loiseau, Irene 1

1 Departamento de Computación – Facultad de Ciencias Exactas y Naturales – Universidad de Buenos Aires, Argentina; Partially supported by grants UBACYT EX036, CONICET 644/98. 
@article{RO_2003__37_2_67_0,
     author = {Maculan, Nelson and Passini, Marcos de Mendon\c{c}a and Brito, Jos\'e Andr\'e de Moura and Loiseau, Irene},
     title = {Column-generation in integer linear programming},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {67--83},
     publisher = {EDP-Sciences},
     volume = {37},
     number = {2},
     year = {2003},
     doi = {10.1051/ro:2003014},
     mrnumber = {2010413},
     zbl = {1036.90076},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ro:2003014/}
}
TY  - JOUR
AU  - Maculan, Nelson
AU  - Passini, Marcos de Mendonça
AU  - Brito, José André de Moura
AU  - Loiseau, Irene
TI  - Column-generation in integer linear programming
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2003
SP  - 67
EP  - 83
VL  - 37
IS  - 2
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ro:2003014/
DO  - 10.1051/ro:2003014
LA  - en
ID  - RO_2003__37_2_67_0
ER  - 
%0 Journal Article
%A Maculan, Nelson
%A Passini, Marcos de Mendonça
%A Brito, José André de Moura
%A Loiseau, Irene
%T Column-generation in integer linear programming
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2003
%P 67-83
%V 37
%N 2
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ro:2003014/
%R 10.1051/ro:2003014
%G en
%F RO_2003__37_2_67_0
Maculan, Nelson; Passini, Marcos de Mendonça; Brito, José André de Moura; Loiseau, Irene. Column-generation in integer linear programming. RAIRO - Operations Research - Recherche Opérationnelle, Tome 37 (2003) no. 2, pp. 67-83. doi: 10.1051/ro:2003014

Cité par Sources :