Teoría poliédrica en programación lineal entera

Abstract

La programación lineal entera es una rama importante de la programación lineal en la que las variables toman valores enteros, lo que dificulta la búsqueda de la solución óptima. Sin embargo, se emplea en diferentes ámbitos con el fin de optimizar una función objetivo sujeta a una serie de restricciones. Este trabajo se centra en dar una descripción ideal de la envolvente convexa de la región factible y acercarnos lo más posible a la solución óptima del problema mediante la utilización de algoritmos de corte. En el primer capítulo se presentan definiciones y resultados fundamentales de la teoría poliédrica, además de la formulación de los diferentes tipos de problemas de programación entera (pura, mixta y binaria) y el Teorema de Meyer, resultado principal de este capítulo. El Capítulo 2 se centra en la resolución efectiva de problemas de programación entera, debido a que se conoce la descripción completa de la envolvente convexa. Se estudian los conceptos de poliedro entero y matrices unimodulares y se analizan los problemas de transporte y flujo de redes. En el tercer capítulo se profundiza en la descripción parcial de la envolvente convexa mediante familias de desigualdades, se introducen los conceptos de desigualdades válidas, relajaciones y cortes. Se detalla el algoritmo de planos de corte, como herramienta para aproximarse a la solución óptima de un problema de programación entera. Y finalmente se da una lista con una breve explicación de algunas familias de desigualdades. Por último en el Capítulo 4 se tratan los cortes de Gomory, el algoritmo de cortes fraccionarios de Gomory tanto para el problema de programación entera puro como para el mixto, y se estudia la efectividad de dicho algoritmo para llegar a una solución óptima en un número finito de iteraciones.

Integer linear programming is an important branch of linear programming in which variables take on integer values, making it difficult to find the optimal solution. However, it is used in different areas in order to optimize an objective function subject to a series of constraints. This work focuses on giving an ideal description of the convex envelope and getting as close as possible to the optimal solution of the problem by using cutting algorithms. In the first chapter, definitions and fundamental results of polyhedral theory are presented, as well as the formulation of the different types of integer programming problems (pure, mixed and binary) and Meyer’s Theorem, the main result of this chapter, is presented. Chapter 2 focuses on the effective resolution of integer programming problems, as the complete description of the convex envelope is known. The concepts of integer polyhedron and unimodular matrices are studied and the problems of transport and network flow are analyzed. In the third chapter, the partial description of the convex envelope is deepened by means of families of inequalities, the concepts of valid inequalities, relaxations and cuts are introduced. The cutting plane algorithm is detailed as a tool to approximate the optimal solution of an entire programming problem. And finally a list is given with a brief explanation of some families of inequalities. Finally, Chapter 4 deals with Gomory cuts, Gomory’s fractional cut algorithm for both the pure and mixed integer programming problem, and studies the effectiveness of this algorithm to arrive at an optimal solution in a finite number of iterations.