Column-generation in integer linear programming

Mostrar todas las versiones(3)

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 ord...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Maculan, N., De Mendonça Passini, M., De Moura Brito, J.A., Loiseau, I.
Formato: JOUR
Materias:
Branch-and-price
Column-generation
Integer programming
Binary sequences
Computational geometry
Computational methods
Problem solving
Telecommunication networks
Vectors
Binary column vectors
Column generation
Integer linear programming
Integer problems
Linear programming
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_03990559_v37_n2_p67_Maculan
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
Descripción
Sumario: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. © EDP Sciences 2003.

Ejemplares similares