INTEGER PROGRAMMING

Author: SIMON DE BLAS CLARA.
Year: 2003.
University: COMPLUTENSE DE MADRID [www.ucm.es].
Place of defense: FACULTAD DE CC. MATEMÁTICAS.
Place of preparation: FACULTAD DE CIENCIAS MATEMATICAS.

Summary: This monograph is devoted to classic problems of the Operations Research under a different approach: the optimization of the largest ratios of the problem. The difficulty of addressing this objective under problems that already are unsolvable in a reasonable computational time ago which now is almost unexplored. Have been selected for their envergarudra transport problems, quadratic and allocation of routes to expand their study and offer alternatives to a classic goal, as is the optimization of the sum of the components of the coefficients of the problem. It is considered in this paper the problem of congestion as defined by Burkard in 1973 with the alternative formulation of Punnen and for the quadratic problem. We present algorithms resolution, both general and rough, and his approach through the Theory Grafos. We present different theorems classic in the literature that allow characterize the optimal solutions under a common approach set out in the paper, a General Theory of Bottling. It discusses the different cases: transportation, placement, location, traveler, lexicográfico, petition, tree stand biconexo, capacity, minimal road, matching trees Steiner and its variants, bandwidth, among others. Finally presents the most remarkable applications exist in the literature.

Author: MERINO MAESTRE MARÍA.
Year: 2004.
University: PAÍS VASCO [www.ehu.es].
Place of defense: FACULTAD DE CIENCIAS ECONÓMICAS Y EMPRESARIALES (BILBAO).
Place of preparation: FACULTAD DE CIENCIAS ECONÓMICAS Y EMPRESARIALES (BILBAO).

Summary: The work was conducted the following aspects: First, it seeks to explain the interest of the Stochastic Programming in general and its application in the financial and economic world in particular. It describes the fundamental concepts, technologies modeling, methods of resolution and the many applications of this discipline. Secondly, in the field of stochastic modeling, pursued generalize concepts defined in linear models bietapa to models multistage mixed 0-1, incorporate measures of risk, as well as to contrast the goodness of stochastic solution proposed in front of the deterministic based on the stage average. Thirdly, in terms of methodologies resolution in optimization under uncertainty, is designed and contrasts with the relevant experience computational algorithms decomposition of stochastic modeling mixed 0-1, both for the case bietápico as multistage, all of them large . Finally, it describes, modeled and solved in an efficient two applications in the financial field. The first consists of structuring a portfolio of securities collateralized mortgage under uncertainty and the second deals with the management of a portfolio of assets and liabilities of debt under uncertainty.

Author: Plana Andani Isaac.
Year: 2004.
University: VALENCIA [www.uv.es].
Place of defense: Facultad de Matemáticas.
Place of preparation: Facultad de Matemáticas.

Summary: In this thesis, we have studied the Problem General Routes Wind (WGRP). The problem is, given a graph G = (V, E), with a set of vertices V, a set of two costs edges E c (i, j), c (j, i) associated with each edge, one by sense tour, and given a subset of vertices belonging to V VR required a subset of edges required ER included in E, find a tour least cost to tour at least once every edges required and visit all the vertices required. This problem has a dual interest, because modeling real-life situations, including details of an example in this memory, and at the same time, generalized to most problems routes by Arcos with a single vehicle conocidos.Hemos studied the polyhedron associated space solutions to the problem, describing the following families esigualdades and demonstrating that define facet of polyhedra: trivial inequalities, inequalities of compulsion, esigualdades connectivity, inequalities cuts R-impares, inequalities KC and K-C02, inequalities Path- Bridge and Path-Bridge02 and inequalities Honeycomb and Honeycomb02.También have introduced a `` facelift''theorem, which states that all inequalities configuration inducing facet for WGRP in the graph configuration also induces facet of WGRP in the original graph . However, we have seen that not all the inequalities that induce facet of polyhedron of WGRP are inequalities configuration, so we have introduced the concept of inequality configuration weak. We have also introduced a new family of valid inequalities that induce facets for WGRP called Zigzag, and that fall into this new category of inequality. We have studied the implementation of these new inequalities in other problems that are particular cases of WGRP, and under what conditions are valid and induce facets in these problemas.Para's resolution WGRP, we have implemented an algorithm branching and Court (Branch & Cut), which incorporates, among others, a new heuristic algorithm separation designed to identify a certain type of inequalities Zigzag raped. We have used a number of techniques to improve the efficiency of the algorithm Branch & Cut, such as branching restrictions, tailing-off, filtering inequalities and the resumption with upper artificial.Este algorithm Court branching and has been tested on a large number of instances of very different characteristics. Some of them, the largest, have been randomly generated for this work, while others have been taken from the literature. Not only have we used the behest of WGRP, but also problems that appear as individual cases, such as WRPP, MGRP, MRPP, GRP and WGPS. The sizes of the bodies vary from 7 to 1000 nodes, from 10 to 4000 edges, and from 1 to 480 components R-conexas. The algorithm has been able to solve in a matter of seconds instances of small size and in a few minutes the medium in size. Most of the larger bodies also were resolved best, and only for some of the most difficult and with the greatest number of components R-conexas algorithm has been unable to reach the soluciónóptima in a time limit of 10 hours, although the gap means in these sets of bodies remains below 0.7%.

Author: OJEDA RODRIGUEZ JORDI.
Year: 2004.
University: POLITÉCNICA DE CATALUÑA [www.upc.edu].
Place of defense: ETSEIB.
Place of preparation: ETSEIB, EDIFICI H Campus SUD.

Summary: The aim of the thesis is to solve in an efficient allocation of hours per week for workers of a multipurpose service center, with the proviso priority to ensure a minimum capacity in each of the periods (hours, half-hours, etc. .), which considers divided week (horizon programming used), and seeking to achieve a desired capacity, in each period, taking into account the preferences of workers for a few other times and the allocation of priorities types of tasks depending on the category of workers. The versatility is that an employee of a class can perform one or more types of tasks. The priority indicated how they wished to make the allocation of the kinds of tasks in the case of versatility, in this way, is assigned the highest priority to the task of the category of worker. Consideration will also be given the efficiency presenting the different categories of workers to perform different types of tasks can be performed, depending on the versatility considered or accepted. The basic facts of the problem are as follows:-Relationship workers with the following information for each of them: class schedules and list of eligible and preferences. - Types of tasks can be performed by the workers in each category, and priority and efficiency for each pair categoría-tarea. - Capacity minimum for each type of task, in each time horizon of programming (hour, half hour, and so on.). - Capacity desired for each type of work (which must be greater than or equal to the minimum capacity), in each time horizon of programming. - The relative importance of different elements to be considered in the objective function. The function is to optimize complex, as it considered several objectives:-To minimize the deviations of capacity resulting in the capacity desired. - Maximize the preferences of workers to assign schedules. - Maximize the priorities in allocating the kinds of tasks to categories. Furthermore, it is essential to ensure a minimum capacity in each period, since they would otherwise not be able to function properly service center, and bring the resulting capacity to the maximum extent possible the capability desired, using a nonlinear penalty associated with deficit and surplus capacity. Ultimately, it comes to approximate the presence of workers who provide the solution to the desired capacity, ensuring the satisfaction of those workers. The thesis presents a mathematical programming model and a mixed heuristic procedure. A total of nine experiments are performed to produce different conclusions.

Author: Piñana Manuel Estefanía.
Year: 2005.
University: VALENCIA [www.uv.es].
Place of defense: Facultad de Matemáticas.
Place of preparation: Facultad de Matemáticas.

Summary: The minimization of bandwidth is a classical problem of optimization. It originated in the 50's in the context of computational manipulation of matrices within the structural engineering field. This problem is equivalent to the problem of bandwidth for graphs. Its applications include: simplification of the process of solving systems of equations by the method of elimination of Gauss, the design of power transmission systems, circuit design, approximate solutions of equations in partial derivatives or management and retrieving information in hypertext. If we define the bandwidth of any one row of a matrix as the maximum distances of the non-zero elements of this row to the main diagonal, the bandwidth of a matrix is defined as the maximum widths of all its rows. The goal is to reduce the bandwidth of the matrix to the greatest extent possible, through permutations of rows and columns. In chapter 1 we present a more detailed description of the problem and its applications, as well as the general outlines of the methodologies used for problem solving. In chapter 2 we present an algorithm based on the methodologies GRASP (Greedy Randomized Adaptive Search Procedure) and Path Relinking. Chapter 3 focuses on the exact resolution of the problem. On one side are some theoretical results (specifically an integer linear formulation of the problem and some partial orderings for heights), and, secondly, we describe the algorithm that follows the methodology Branch and Bound and we have designed specifically for this problem. Finally, we studied the methods of exploration based on memory usage. We have proposed two new methods, based on a search Taboo and another based on the methodology Search Dispersa. We have also done a study on the contribution of some key elements in the search heuristics. These methods constitute Chapter 4 of this thesis. All designed methods have been tested on a collection of instances of free distribution (Harwell-Boeing Sparse Matrix Collection), which had already been used in the literature. The results were compared with those obtained by the methods more competitive, getting very favorable results.