[pt] Esta tese generaliza a variante multi-período do clássico problema da Árvore de Steiner com coleta de prêmios (PCST), que visa encontrar um subgrafo conexo que maximize os prêmios recuperados de nós conectados menos o custo de utilização das arestas conectadas. Este trabalho adicionalmente: (a) permite que vértices sejam conectados à árvore em diferentes períodos de tempo; (b) impõe um orçamento pré-definido em arestas selecionadas em um horizonte específico de períodos de tempo; e (c) limita o comprimento total de arestas que podem ser adicionadas em um período de tempo. Um algoritmo branch-and-cut é fornecido para este problema, avaliando satisfatoriamente instâncias benchmark da literatura, adaptadas para uma configuração multi-período, de até aproximadamente 2000 vértices e 200 terminais em tempo razoável. / [en] This thesis generalizes the multi-period variant of the classical Prizecollecting Steiner Tree Problem, which aims at finding a connected subgraph that maximizes the revenues collected from connected nodes minus the costs to utilize the connecting edges. This work additionally: (a) allows vertices to be added to the tree at different time periods; (b) imposes a predefined budget on edges selected over a specific horizon of time periods; and (c) limits the total length of edges that can be added over a time period. A branch-and-cut algorithm is provided for this problem, satisfactorily evaluating benchmark instances from the literature, adapted to a multi-period setting, up to approximately 2000 vertices and 200 terminals in reasonable time.

Norrmejerier står inför förändringar vad gäller både mjölkkonsumtion och flytt av produktionen från Luleå mejeri till Umeå mejeri inom en snar framtid. Det har gett behov av ett verktyg för att snabbt kunna fatta beslut om systemet kan hantera en ökad mängd volym och antal produktkategorier. För att ta fram ett sådant verktyg skapades en matematisk optimeringsmodell uppbyggd i programvaran Python som gör det möjligt att köra programmet för olika scenarion. Modellen använder optimeringslösaren Pulp för att hitta en lösning på problemet. Den matematiska modellen baseras på Multi Commodity Flow Problem med tidsvariabel i kombination med Flow-shop scheduling och har modifierats efter systemet på Umeå mejeri. Det är en pessimistisk modell baserat på de antaganden som gjorts i rapporten. Programmet baseras på ett dygns produktion och avgör, genom att minimera den totala tiden det tar för flödet genom processen, om det finns kapacitet för en ökad produktion. Systemet i projektet är uppdelat i två subnätverk på grund av tidskomplexiteten och resultaten visar att implementering av en ytterligare produktkategori kan hanteras av båda subnätverken. En ökad volym med 10% av den befintliga kan endast hanteras av den första delen av nätverket. Det betyder att det finns tekniska begränsningar i det andra subnätverket. Genom tillägg av extra noder som kan användas till en viss straffkostnad kunde flaskhalsar identifieras och det visade sig att pastör 2P1 är en uppenbar flaskhals i systemet. Om man ökar produktionen ytterligare kan även silosarna behöva utökas för att hantera flödet. / Norrmejerier is facing changes in terms of both milk consumption and a move of the production from Luleå dairy to Umeå dairy in the near future. This has given rise to the need of a tool that quickly can make descisions about whether the system can handle an increased amount of volume and number of product categories. To produce such a tool a mathematical optimization model was created in Python which makes it possible to run the program for different scenarios. The model uses the optimization solver Pulp. The mathematical model is based on Multi Commodity Flow Problem with time variable combined with Flow-shop scheduling and has been modified according to the system at Umeå dairy. Based on the assumptions made in the report it is a pessimistic model. The program is based on one day's production and determines by minimizing the total time it takes for the flow to pass through the system, to see if there is enough capacity for increased production. The system in the project is divided into two subnetworks due to the time complexity and the results show that implementation of an additional product category can be handled by both subnetworks. An increased volume of 10% of the existing volume can only be handled by the first part of the network. This means that there are technical limitations in the second subnetwork. By adding extra nodes that can be used for a certain penalty cost, bottlenecks could be identified and it turned out that Pasteur 2P1 is an obvious bottleneck in the system. If the production increases further the silos may also need to be expanded to handle the flow in the system.

Dans cette thèse, nous nous intéressons aux problèmes du knapsack multidimensionnel à choix multiple. Ils interviennent essentiellement en télécommunication. Nous proposons de nouvelles méthodes hybrides de résolution exacte et approchée. Dans un premier temps, nous proposons des méthodes heuristiques en se basant sur les techniques de génération de colonnes et d'arrondi. Ensuite, nous abordons une méthode de recherche locale, dite méthode de branchement local, où des contraintes linéaires sont introduites pour intensifier et diversifier la recherche. Cette méthode est ensuite hybridée avec la génération de colonnes et une technique d'arrondi. Concernant la résolution exacte, nous nous basons sur une méthode de "Branch and cut". Nous commençons par proposer de nouvelles contraintes valides pour le problème. Ensuite, nous les associons à des contraintes de couverture locales et globales dans un schéma énumératif. Les approches heuristiques et l'algorithme exact que nous proposons sont comparés à d'autres heuristiques de la littérature et au Solveur de programmes linéaires Cplex . L'ensemble de ces tests numériques ont été menés sur des instances ardues de la littérature ainsi que sur des instances générées aléatoirement de taille modérée.

La résolution jusqu'à l'optimalité de problèmes d'optimisation combinatoire NP-difficiles nécessite une mise en oeuvre de méthodes de plus en plus complexes qui consomment de plus en plus de puissance de calcul. L'objectif de notre travail est de paralléliser un algorithme de "Branch and Cut" pour résoudre jusqu'à l'optimalité des instances difficiles du voyageur de commerce. Dans la première partie de notre travail, nous présentons les composantes principales de l'algorithme du "Branch and Cut". Nous étudions ensuite le problème du voyageur de commerce par une approche polyédrale. Nous donnons enfin une description détaillée de notre implémentation de l'algorithme du "Branch and Cut". Dans la deuxième partie, Nous commençons par une brève présentation du parallélisme, et un état de l'art des études menées sur la parallélisation de l'algorithme du "Branch and Bound". Puis, nous proposons plusieurs modèles de parallélisations de l'algorithme du "Branch and Cut". Nous décrivons ensuite la stratégie de contrôle de la recherche arborescente qu'on a adopté, les mécanismes de minimisation des coûts liés aux différentes étapes de la communication entre les processeurs et les stratégies d'équilibrages. Nous terminons en donnant les résultats obtenus sur le IBM-SP1.

We consider combinatorial t-design problems as discrete optimization problems. Our motivation is that only a few studies have been done on the use of exact optimization techniques in designs, and that classical methods in design theory have still left many open existence questions. Roughly defined, t-designs are pairs of discrete sets that are related following some strict properties of size, balance, and replication. These highly structured relationships provide optimal solutions to a variety of problems in computer science like error-correcting codes, secure communications, network interconnection, design of hardware; and are applicable to other areas like statistics, scheduling, games, among others. We give a new approach to combinatorial t-designs that is useful in constructing t-designs by polyhedral methods. The first contribution of our work is a new result of equivalence of t-design problems with a graph theory problem. This equivalence leads to a novel integer programming formulation for t-designs, which we call GDP. We analyze the polyhedral properties of GDP and conclude, among other results, the associated polyhedron dimension. We generate new classes of valid inequalities to aim at approximating this integer program by a linear program that has the same optimal solution. Some new classes of valid inequalities are generated as Chv´atal-Gomory cuts, other classes are generated by graph complements and combinatorial arguments, and others are generated by the use of incidence substructures in a t-design. In particular, we found a class of valid inequalities that we call stable-set class that represents an alternative graph equivalence for the problem of finding a t-design. We analyze and give results on the strength of these new classes of valid inequalities. We propose a separation problem and give its integer programming formulation as a maximum (or minimum) edge-weight biclique subgraph problem. We implement a pure cutting-plane algorithm using one of the stronger classes of valid inequalities derived. Several instances of t-designs were solved efficiently by this algorithm at the root node of the search tree. Also, we implement a branch-and-cut algorithm and solve several instances of 2-designs trying different base formulations. Computational results are included.

The minimum k-partition (MkP) problem is a well-known optimization problem encountered in various applications most notably in telecommunication and physics. Formulated in the early 1990s by Chopra and Rao, the MkP problem is the problem of partitioning the set of vertices of a graph into k disjoint subsets so as to minimize the total weight of the edges joining vertices in different partitions. In this thesis, we design and implement a branch-and-cut algorithm based on semidefinite programming (SBC) for the MkP problem. We describe and study the properties of two relaxations of the MkP problem, the linear programming and the semidefinite programming relaxations. We then derive a new strengthened relaxation based on semidefinite programming. This new relaxation provides tighter bounds compared to the other two discussed relaxations but suffers in term of computational time. We further devise an iterative clustering heuristic (ICH), a novel heuristic that finds feasible solution to the MkP problem and we compare it to the hyperplane rounding techniques of Goemans and Williamson and Frieze and Jerrum for k=2 and for k=3 respectively. Our computational results support the conclusion that ICH provides a better feasible solution for the MkP. Furthermore, unlike the hyperplane rounding, ICH remains very effective in the presence of negative edge weights. Next we describe in detail the design and implementation of a branch-and-cut algorithm based on semidefinite programming (SBC) to find optimal solution for the MkP problem. The ICH heuristic is used in our SBC algorithm to provide feasible solutions at each node of the branch-and-cut tree. Finally, we present computational results for the SBC algorithm on several classes of test instances with k=3, 5, and 7. Complete graphs with up to 60 vertices and sparse graphs with up to 100 vertices arising from a physics application were considered.

The minimum k-partition (MkP) problem is a well-known optimization problem encountered in various applications most notably in telecommunication and physics. Formulated in the early 1990s by Chopra and Rao, the MkP problem is the problem of partitioning the set of vertices of a graph into k disjoint subsets so as to minimize the total weight of the edges joining vertices in different partitions. In this thesis, we design and implement a branch-and-cut algorithm based on semidefinite programming (SBC) for the MkP problem. We describe and study the properties of two relaxations of the MkP problem, the linear programming and the semidefinite programming relaxations. We then derive a new strengthened relaxation based on semidefinite programming. This new relaxation provides tighter bounds compared to the other two discussed relaxations but suffers in term of computational time. We further devise an iterative clustering heuristic (ICH), a novel heuristic that finds feasible solution to the MkP problem and we compare it to the hyperplane rounding techniques of Goemans and Williamson and Frieze and Jerrum for k=2 and for k=3 respectively. Our computational results support the conclusion that ICH provides a better feasible solution for the MkP. Furthermore, unlike the hyperplane rounding, ICH remains very effective in the presence of negative edge weights. Next we describe in detail the design and implementation of a branch-and-cut algorithm based on semidefinite programming (SBC) to find optimal solution for the MkP problem. The ICH heuristic is used in our SBC algorithm to provide feasible solutions at each node of the branch-and-cut tree. Finally, we present computational results for the SBC algorithm on several classes of test instances with k=3, 5, and 7. Complete graphs with up to 60 vertices and sparse graphs with up to 100 vertices arising from a physics application were considered.

This thesis deals with the exact solution of large-scale minimum bisection problems via a semidefinite relaxation in a branch-and-cut framework. After reviewing known results on the underlying bisection cut polytope a study of new facet-defining inequalities is presented. They are derived from the known knapsack tree inequalities. We investigate strengthenings based on the new cluster weight polytope and present polynomial separation algorithms for special cases. The dual of the semidefinite relaxation of the minimum bisection problem is tackled in its equivalent form as an eigenvalue optimisation problem with the spectral bundle method. Implementational details regarding primal heuristics, branching rules, so-called support extensions for cutting planes and warm start are presented. We conclude with a computational study in which we show that our approach is competetive to state-of-the-art implementations using linear programming or semidefinite programming relaxations. / Diese Dissertation befasst sich mit der exakten Lösung großer Minimum Bisection Probleme über eine semidefinite Relaxierung in einem Branch-and-Cut Zugang. Nachdem bekannte Resultate zum zugrundeliegenden Bisection Cut Polytop dargestellt wurden, wird eine Studie neuer facettendefinierender Ungleichungen präsentiert. Diese werden von den bekannten Knapsack Tree Ungleichungen abgeleitet. Wir untersuchen Verstärkungen basierend auf dem neuen Cluster Weight Polytop und zeigen polynomiale Separierungsalgorithmen für Spezialfälle. Die Duale der semidefiniten Relaxierung des Minumum Bisection Problems wird in ihrer äquivalenten Form als Eigenwertoptimierungsproblem mit dem Spektralen Bündelverfahren bearbeitet. Details der Implementierung bezüglich primaler Heuristiken, Branchingregeln, sogenannter Supporterweiterungen für die Schnittebenen und Warmstart werden präsentiert. Wir beenden die Arbeit mit einer numerischen Studie, in der wir zeigen, dass unser Zugang konkurrenzfähig zu aktuellen Implementationen basierend auf linearen und semidefiniten Relaxierungen ist.

We consider combinatorial t-design problems as discrete optimization problems. Our motivation is that only a few studies have been done on the use of exact optimization techniques in designs, and that classical methods in design theory have still left many open existence questions. Roughly defined, t-designs are pairs of discrete sets that are related following some strict properties of size, balance, and replication. These highly structured relationships provide optimal solutions to a variety of problems in computer science like error-correcting codes, secure communications, network interconnection, design of hardware; and are applicable to other areas like statistics, scheduling, games, among others. We give a new approach to combinatorial t-designs that is useful in constructing t-designs by polyhedral methods. The first contribution of our work is a new result of equivalence of t-design problems with a graph theory problem. This equivalence leads to a novel integer programming formulation for t-designs, which we call GDP. We analyze the polyhedral properties of GDP and conclude, among other results, the associated polyhedron dimension. We generate new classes of valid inequalities to aim at approximating this integer program by a linear program that has the same optimal solution. Some new classes of valid inequalities are generated as Chv´atal-Gomory cuts, other classes are generated by graph complements and combinatorial arguments, and others are generated by the use of incidence substructures in a t-design. In particular, we found a class of valid inequalities that we call stable-set class that represents an alternative graph equivalence for the problem of finding a t-design. We analyze and give results on the strength of these new classes of valid inequalities. We propose a separation problem and give its integer programming formulation as a maximum (or minimum) edge-weight biclique subgraph problem. We implement a pure cutting-plane algorithm using one of the stronger classes of valid inequalities derived. Several instances of t-designs were solved efficiently by this algorithm at the root node of the search tree. Also, we implement a branch-and-cut algorithm and solve several instances of 2-designs trying different base formulations. Computational results are included.

University, Diss., 1999--Saarbrücken.