INTEGER PROGRAMMATION

Auteur: SIMON DE BLAS CLARA.
Année: 2003.
Université: COMPLUTENSE DE MADRID [www.ucm.es].
Lieu de l'exposition: FACULTAD DE CC. MATEMÁTICAS.
Lieu de préparation: FACULTAD DE CIENCIAS MATEMATICAS.

Résumé: Cette monographie est consacrée à des problèmes classiques de la recherche opérationnelle dans le cadre d'une approche différente: l'optimisation des ratios les plus importants du problème. La difficulté d'aborder les problèmes sous cet objectif que sont déjà insolubles dans un temps de calcul raisonnable, il ya ce qui est maintenant presque inexplorée. Ont été sélectionnés pour leur envergarudra les problèmes de transport, du second degré et de la répartition des voies à élargir leur étude et de proposer des alternatives à un objectif classique, comme l'optimisation de la somme des composantes des coefficients du problème. Il est examiné dans le présent document, le problème de la congestion, tels que définis par Burkard en 1973 avec la variante de Punnen et pour le problème quadratique. Nous présentons des algorithmes de résolution, à la fois général et rugueux, et son approche à travers la théorie Grafos. Nous présentons les différents théorèmes classiques de la littérature qui permettent de caractériser les solutions optimales dans le cadre d'une approche commune énoncés dans le document, une théorie générale de mise en bouteille. Il examine les différents cas: le transport, de placement, de l'emplacement, voyageur, lexicográfico, pétition, biconexo arbre debout, la capacité, le minimum de la route, le rapprochement des arbres Steiner et ses variantes, de bande passante, entre autres. Enfin présente les plus remarquables d'applications existent dans la littérature.

Auteur: MERINO MAESTRE MARÍA.
Année: 2004.
Université: PAÍS VASCO [www.ehu.es].
Lieu de l'exposition: FACULTAD DE CIENCIAS ECONÓMICAS Y EMPRESARIALES (BILBAO).
Lieu de préparation: FACULTAD DE CIENCIAS ECONÓMICAS Y EMPRESARIALES (BILBAO).

Résumé: Les travaux ont été menés sur les aspects suivants: Premièrement, il cherche à expliquer l'intérêt de la programmation stochastique en général et son application dans le monde financier et économique en particulier. Il décrit les concepts fondamentaux, les techniques de modélisation, les méthodes de résolution et les nombreuses applications de cette discipline. Deuxièmement, dans le domaine de la modélisation stochastique, poursuivi généraliser les concepts définis dans les modèles linéaires bietapa à plusieurs modèles mixtes 0-1, incorporer des mesures de risque, ainsi que de mettre en contraste la bonté de stochastique solution proposée devant la déterministes fondées sur la scène Moyenne. Troisièmement, sur le plan de l'optimisation des méthodes de résolution en vertu de l'incertitude, est conçue et contraste avec l'expérience pertinente de calcul des algorithmes de décomposition de modélisation stochastique mixte 0-1, à la fois pour le cas bietápico comme plusieurs, tous des grands. Enfin, il décrit, à la modélisation et à résoudre de façon efficace deux applications dans le domaine financier. La première consiste à structurer un portefeuille de titres hypothécaires garantis en vertu de l'incertitude et le second traite de la gestion d'un portefeuille d'actifs et de passifs de la dette au titre de l'incertitude.

Auteur: Plana Andani Isaac.
Année: 2004.
Université: VALENCIA [www.uv.es].
Lieu de l'exposition: Facultad de Matemáticas.
Lieu de préparation: Facultad de Matemáticas.

Résumé: Dans cette thèse, nous avons étudié le problème général Routes Vent (WGRP). Le problème est, étant donné un graphe G = (V, E), avec un ensemble de sommets V, un ensemble de deux bords coûts Ec (i j) quater (-j, soit i) associés à chaque bord, un par sens tournée , Et étant donné un sous-ensemble de sommets appartenant à V VR besoin d'un sous-ensemble de bords requis ER inclus dans E, trouver une tournée au moindre coût pour visiter au moins une fois tous bords nécessaires et visiter tous les sommets nécessaires. Ce problème a un double intérêt, car la modélisation de situations de la vie réelle, y compris des détails sur un exemple dans ce mémoire, et en même temps, généralisé à la plupart des problèmes de liaisons par Arcos avec un seul véhicule conocidos.Hemos étudié le polyèdre associé à l'espace des solutions Le problème, décrivant les familles ci-dessous esigualdades et démontrer que les définissent les aspects de polyèdres: futile inégalités, les inégalités de contrainte, esigualdades connectivité, les inégalités coupes R - impares, les inégalités KC et K - C02, les inégalités Path - Pont et le chemin - Bridge02 et les inégalités d'abeille Et Honeycomb02.También ont introduit un `` facelift''theorem, qui stipule que toutes les inégalités de configuration induisant facette de WGRP dans le graphique de configuration également induit facette de WGRP dans l'original graphique. Toutefois, nous avons constaté que toutes les inégalités qui induisent facette du polyèdre de WGRP sont les inégalités de configuration, nous avons donc introduit la notion d'inégalité de configuration faible. Nous avons également introduit une nouvelle famille de validité inégalités qui induisent facettes pour WGRP appelé Zigzag, et qui entrent dans cette nouvelle catégorie de l'inégalité. Nous avons étudié l'application de ces nouvelles inégalités dans les autres problèmes qui sont des cas particuliers de WGRP, et dans quelles conditions sont valables et inciter les facettes de ces problemas.Para l 'résolution WGRP, nous avons mis en œuvre un algorithme de branchement et de la Cour (Branch Et coupe), qui comprend, entre autres, un nouvel algorithme heuristique de séparation conçu pour identifier un certain type d'inégalités Zigzag violées. Nous avons utilisé un certain nombre de techniques pour améliorer l'efficacité de l'algorithme Branch & Cut, tels que les restrictions de branchement, résidus décollage, le filtrage des inégalités et de la reprise de la Cour supérieure de artificial.Este algorithme de branchement et a été testé sur un grand nombre de Les instances de caractéristiques très différentes. Certains d'entre eux, le plus important, ont été généré aléatoirement pour ce travail, alors que d'autres ont été tirées de la littérature. Non seulement nous avons utilisé la demande du WGRP, mais aussi des problèmes qui apparaissent comme des cas individuels, tels que WRPP, MGRP, MRPP, GRP et GTSP. La taille des organes varient de 7 à 1000 noeuds, de 10 à 4000 bords, et de 1 à 480 éléments R - conexas. L'algorithme a été capable de résoudre en quelques secondes les instances de petite taille et, en quelques minutes, la moyenne taille. La plupart des grands organismes ont également résolu le meilleur des cas, et seulement pour certains des plus difficiles et avec le plus grand nombre de composants R - conexas algorithme a été impossible de joindre le soluciónóptima dans un délai de 10 heures, bien que l'écart moyen dans ces Ensembles d'organes reste inférieure à 0,7%.

Auteur: OJEDA RODRIGUEZ JORDI.
Année: 2004.
Université: POLITÉCNICA DE CATALUÑA [www.upc.edu].
Lieu de l'exposition: ETSEIB.
Lieu de préparation: ETSEIB, EDIFICI H Campus SUD.

Résumé: L'objectif de cette thèse est de résoudre de manière efficace l'allocation d'heures par semaine pour les travailleurs d'un centre de services polyvalents, à la condition prioritaire d'assurer un minimum de capacité dans chacune des périodes (heures, les demi-heures, etc.) Qui considère divisé semaine (horizon de programmation utilisé), et en cherchant à atteindre une capacité désirée, dans chaque période, en tenant compte des préférences des travailleurs pour quelques autres fois, et l'allocation de priorités types de tâches en fonction de la catégorie de travailleurs. La polyvalence est que l'employé d'une classe peuvent effectuer un ou plusieurs types de tâches. La priorité indiqué comment ils souhaitaient faire de la répartition des types de tâches dans le cas de la polyvalence, de cette manière, est attribué la plus haute priorité à la tâche de la catégorie de travailleurs. On tiendra aussi compte tenu de l'efficacité de présenter les différentes catégories de travailleurs pour effectuer les différents types de tâches peuvent être réalisées, en fonction de la polyvalence considérée ou acceptée. Les faits de base du problème sont les suivantes: - Relations avec les travailleurs les renseignements suivants pour chacun d'entre eux: les horaires de classe et de la liste des admissibles et préférences. - Types de tâches peuvent être effectués par les travailleurs dans chaque catégorie, et de la priorité et de l'efficacité pour chaque paire categoria - tarea. - Capacité minimum pour chaque type de tâche, dans chaque horizon de programmation (heure, demi-heure, et ainsi de suite.). - Capacité souhaitée pour chaque type de travail (qui doit être supérieure ou égale à la capacité minimale), dans chaque horizon de la programmation. - L'importance relative des différents éléments à prendre en considération dans la fonction objective. La fonction est d'optimiser complexe, comme il a examiné plusieurs objectifs: - Pour réduire les écarts de capacité résultant de la capacité désirée. - Maximiser les préférences des travailleurs à affecter les horaires. - Maximiser les priorités dans l'affectation des types de tâches à des catégories. En outre, il est essentiel d'assurer une capacité minimale de chaque période, car ils autrement, ne seraient pas en mesure de fonctionner correctement un centre de service, et de porter la capacité résultant de la mesure possible la capacité désirée, au moyen d'une peine non linéaires associés à l'excédent et de déficit Capacité. En fin de compte, il s'agit de rapprocher la présence de travailleurs qui fournissent la solution à la capacité désirée, assurant la satisfaction de ces travailleurs. Le mémoire présente un modèle de programmation mathématique et d'une procédure heuristique mixte. Au total, neuf expériences sont effectuées afin de produire des conclusions différentes.

Auteur: Piñana Manuel Estefanía.
Année: 2005.
Université: VALENCIA [www.uv.es].
Lieu de l'exposition: Facultad de Matemáticas.
Lieu de préparation: Facultad de Matemáticas.

Résumé: La réduction de la largeur de bande est un problème classique d'optimisation. Il a son origine dans les années 50 dans le cadre du calcul de manipulation de matrices structurelles dans le secteur de l'ingénierie. Ce problème est équivalent au problème de la bande passante pour les graphiques. Ses applications comprennent: la simplification du processus de résolution de systèmes d'équations par la méthode d'élimination de Gauss, de la conception de systèmes de transmission de puissance, de circuits, des solutions approximatives d'équations à dérivées partielles ou de la gestion et de rechercher l'information dans l'hypertexte. Si l'on définit la bande passante de toute une ligne de la matrice que les distances maximales de la non nulle éléments de cette rangée à la diagonale, la bande passante d'une matrice est définie comme la largeur maximale de l'ensemble de ses lignes. L'objectif est de réduire la bande passante de la matrice dans la plus grande mesure possible, dans le cadre de permutations de lignes et colonnes. Dans le chapitre 1, nous présentons une description plus détaillée du problème et de ses applications, ainsi que les grandes lignes des méthodes utilisées pour résoudre les problèmes. Dans le chapitre 2, nous présentons un algorithme fondé sur les méthodes du GRASP (Greedy Randomized Adaptive Search Procedure) et Path Relinking. Le chapitre 3 porte sur la résolution exacte du problème. D'un côté il ya certains résultats théoriques (en particulier un entier linéaire formulation du problème et certains ordres partiels pour les hauteurs), et, d'autre part, nous décrivons l'algorithme qui suit la méthodologie et la Direction Bound et nous avons conçu spécialement pour ce problème. Enfin, nous avons étudié les méthodes d'exploration fondée sur l'utilisation de la mémoire. Nous avons proposé deux nouvelles méthodes, fondées sur une recherche tabou et une autre basée sur la méthodologie de recherche Dispersa. Nous avons également effectué une étude sur la contribution de certains éléments clés dans la recherche heuristique. Ces méthodes constituent le chapitre 4 de cette thèse. Tous conçus méthodes ont été testées sur une collection de cas de la distribution gratuite (Harwell - Boeing Sparse Matrix Collection), qui avait déjà été utilisé dans la littérature. Les résultats ont été comparés à ceux obtenus par les méthodes plus compétitive, obtenir des résultats très favorables.