This chapter introduces exact methods for solving integer linear programming problems with a large number of variables. These methods are known as branch-and price methods. The chapter examines an inequality for eliminating 0-1 column generation and it focuses on two integer linear programming problem models and a comparison between their linear relaxations. The chapter presents a schema of a column generation method for solving an integer linear programming (ILP) and the difficulties that can appear at the time of implementation. In the chapter two column generation algorithms are introduced: for the p-medians problem and for vehicle routing problems. © ISTE Ltd 2014. All rights reserved.
| Documento: | Parte de libro |
| Título: | Column Generation in Integer Linear Programming |
| Autor: | Loiseau, I.; Ceselli, A.; Maculan, N.; Salani, M. |
| Filiación: | Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Argentina Dipartimento di Tecnologie dell'Informazione, Università degli Studi di Milano, Italy Programa de Engenharia de Sistemas e Computação, COPPE, Universidade Federal do Rio de Janeiro, Brazil Dipartimento di Tecnologie dell'Informazione, Università degli Studi di Milano, Italy |
| Palabras clave: | Column generation; Integer linear program (ILP); Vehicle routing; Branch and price; Column generation; Exact methods; Integer Linear Programming; Integer linear programs; It focus; Linear relaxations; Vehicle Routing Problems; Integer programming |
| Año: | 2014 |
| Volumen: | 9781848216563 |
| Página de inicio: | 235 |
| Página de fin: | 259 |
| DOI: | http://dx.doi.org/10.1002/9781119005216.ch9 |
| Título revista: | Concepts of Combinatorial Optimization: 2nd Edition |
| Título revista abreviado: | Concepts of Comb. Optim.: 2nd Ed. |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_97811190_v9781848216563_n_p235_Loiseau |
