2026-04-23T20:28:01Zhttps://uvadoc.uva.es/oai/requestoai:uvadoc.uva.es:10324/632002023-11-24T20:01:47Zcom_10324_38col_10324_852
El algoritmo Branch and Cut en programación lineal entera
Noriega González, Carlos
Álvarez Esteban, Pedro César
Universidad de Valladolid. Facultad de Ciencias
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.
2023-11-24T07:48:43Z
2023-11-24T07:48:43Z
2023
info:eu-repo/semantics/bachelorThesis
https://uvadoc.uva.es/handle/10324/63200
spa
info:eu-repo/semantics/openAccess
http://creativecommons.org/licenses/by-nc-nd/4.0/
Attribution-NonCommercial-NoDerivatives 4.0 Internacional