El algoritmo Branch and Cut en programación lineal entera

Abstract

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.