Por favor, use este identificador para citar o enlazar este ítem:https://uvadoc.uva.es/handle/10324/63200
Título
El algoritmo Branch and Cut en programación lineal entera
Autor
Director o Tutor
Año del Documento
2023
Titulación
Grado en Matemáticas
Resumo
Los problemas de programación lineal entera aparecen en numerosas ocasiones modelando
situaciones del mundo real donde las variables de decisión deben tomar valores enteros.
A nales del siglo pasado se desarrolló el algoritmo de Branch and Cut combinando las
ideas de dos métodos ya conocidos a mediados de siglo, como eran el algoritmo de Branch
and Bound y el método de planos de corte. A lo largo de este trabajo presentaremos los
diferentes tipos de programación lineal, introduciremos brevemente los conceptos básicos
de la teoría de poliedros y del método símplex; y abordaremos los métodos de Branch and
Bound y de planos de corte explicando los algoritmos y tratando todas sus particularidades.
En el penúltimo capítulo llegaremos al objetivo central de este trabajo: entender
cómo funciona el algoritmo de Branch and Cut y los diferentes procesos que se pueden
llevar a cabo previamente para acelerar la búsqueda de la solución óptima utilizando este
método. Finalmente, pondremos en práctica todo lo expuesto en el trabajo planteando
un problema denominado Team Orienteering Problem. Resolveremos este problema utilizando
dos implementaciones diferentes del Branch and Cut, comparando los resultados
obtenidos con ambos enfoques. Integer linear programming problems appear on numerous occasions modelling real-world
situations where the decision variables must take integer values. At the end of the last
century, the Branch and Cut algorithm was developed combining the ideas of two methods
already known in the middle of the century, such as the Branch and Bound algorithm and
the cutting plane method. Throughout this work we will present the di erent types of
linear programming, we will brie y introduce the basic concepts of the theory of polyhedra
and the simplex method; and we will deal with the Branch and Bound and cutting
plane methods, explaining the algorithms and all their peculiarities. In the penultimate
chapter we will reach the central objective of this work: understanding how the Branch
and Cut algorithm works and the di erent processes that can be carried out beforehand
to speed up the search for the optimal solution using this method. Finally, we will put
into practice everything exposed in the work by working with a problem called Team
Orienteering Problem. We will solve this problem using two di erent implementations of
the Branch and Cut, and we will compare the results obtained with both approaches.
Palabras Clave
Branch and Cut
Programación entera
Optimización
Departamento
Departamento de Estadística e Investigación Operativa
Idioma
spa
Derechos
openAccess
Aparece en las colecciones
- Trabajos Fin de Grado UVa [28700]
Arquivos deste item
![Attribution-NonCommercial-NoDerivatives 4.0 Internacional](/themes/Mirage2//images/creativecommons/cc-by-nc-nd.png)