Constructing the genomic median of several given genomes is crucial in developing evolutionary trees, since the genomic median provides an estimate for the ordering of the genes in a common ancestor of the given genomes. This is due to the fact that the content of DNA molecules is often similar, but the difference is mainly in the order in which the genes appear in various genomes. The mutations that affect this ordering are called genome rearrangements, and many structural differences between genomes can be studied using genome rearrangements. In this thesis our main focus is on applying combinatorial optimization techniques to genomic median problems, with particular emphasis on the breakpoint distance as a measure of the difference between two genomes. We will study different variations of the breakpoint median problem from signed to unsigned, unichromosomal to multichromosomal, and linear to circular to mixed. We show how these median problems can be formulated in terms of problems in combinatorial optimization, and take advantage of well-known combinatorial optimization techniques and apply these powerful methods to study various median problems. Some of these median problems are polynomial and many are NP-hard. We find efficient algorithms and approximation methods for median problems based on well-known combinatorial optimization structures. The focus is on algorithmic and combinatorial aspects of genomic medians, and how they can be utilized to obtain optimal median solutions.

Constructing the genomic median of several given genomes is crucial in developing evolutionary trees, since the genomic median provides an estimate for the ordering of the genes in a common ancestor of the given genomes. This is due to the fact that the content of DNA molecules is often similar, but the difference is mainly in the order in which the genes appear in various genomes. The mutations that affect this ordering are called genome rearrangements, and many structural differences between genomes can be studied using genome rearrangements. In this thesis our main focus is on applying combinatorial optimization techniques to genomic median problems, with particular emphasis on the breakpoint distance as a measure of the difference between two genomes. We will study different variations of the breakpoint median problem from signed to unsigned, unichromosomal to multichromosomal, and linear to circular to mixed. We show how these median problems can be formulated in terms of problems in combinatorial optimization, and take advantage of well-known combinatorial optimization techniques and apply these powerful methods to study various median problems. Some of these median problems are polynomial and many are NP-hard. We find efficient algorithms and approximation methods for median problems based on well-known combinatorial optimization structures. The focus is on algorithmic and combinatorial aspects of genomic medians, and how they can be utilized to obtain optimal median solutions.

Constructing the genomic median of several given genomes is crucial in developing evolutionary trees, since the genomic median provides an estimate for the ordering of the genes in a common ancestor of the given genomes. This is due to the fact that the content of DNA molecules is often similar, but the difference is mainly in the order in which the genes appear in various genomes. The mutations that affect this ordering are called genome rearrangements, and many structural differences between genomes can be studied using genome rearrangements. In this thesis our main focus is on applying combinatorial optimization techniques to genomic median problems, with particular emphasis on the breakpoint distance as a measure of the difference between two genomes. We will study different variations of the breakpoint median problem from signed to unsigned, unichromosomal to multichromosomal, and linear to circular to mixed. We show how these median problems can be formulated in terms of problems in combinatorial optimization, and take advantage of well-known combinatorial optimization techniques and apply these powerful methods to study various median problems. Some of these median problems are polynomial and many are NP-hard. We find efficient algorithms and approximation methods for median problems based on well-known combinatorial optimization structures. The focus is on algorithmic and combinatorial aspects of genomic medians, and how they can be utilized to obtain optimal median solutions.

Constructing the genomic median of several given genomes is crucial in developing evolutionary trees, since the genomic median provides an estimate for the ordering of the genes in a common ancestor of the given genomes. This is due to the fact that the content of DNA molecules is often similar, but the difference is mainly in the order in which the genes appear in various genomes. The mutations that affect this ordering are called genome rearrangements, and many structural differences between genomes can be studied using genome rearrangements. In this thesis our main focus is on applying combinatorial optimization techniques to genomic median problems, with particular emphasis on the breakpoint distance as a measure of the difference between two genomes. We will study different variations of the breakpoint median problem from signed to unsigned, unichromosomal to multichromosomal, and linear to circular to mixed. We show how these median problems can be formulated in terms of problems in combinatorial optimization, and take advantage of well-known combinatorial optimization techniques and apply these powerful methods to study various median problems. Some of these median problems are polynomial and many are NP-hard. We find efficient algorithms and approximation methods for median problems based on well-known combinatorial optimization structures. The focus is on algorithmic and combinatorial aspects of genomic medians, and how they can be utilized to obtain optimal median solutions.

No description available.

The p-Median problem (PMP) is one of the most widely applied location problems in urban and regional planning to support spatial decision-making. As an NP-hard problem, the PMP remains challenging to solve optimally, especially for large-sized problems. This research focuses on developing geocomputational approaches to improve the effectiveness and efficiency of solving the PMP. This research also examines existing PMP methods applied to choropleth mapping and proposes a new approach to address issues associated with uncertainty. Chapter 2 introduces a new algorithm that solves the PMP more effectively. In this chapter, a method called the spatial-knowledge enhanced Teitz and Bart heuristic (STB) is proposed to improve the classic Teitz and Bart (TB) heuristic.. The STB heuristic prioritizes candidate facility sites to be examined in the solution set based on the spatial distribution of demand and candidate facility sites. Tests based on a range of PMPs demonstrate the effectiveness of the STB heuristic. Chapter 3 provides a high performance computing (HPC) based heuristic, Random Sampling and Spatial Voting (RSSV), to solve large PMPs. Instead of solving a large-sized PMP directly, RSSV solves multiple sub-PMPs with each sub-PMP containing a subset of facility and demand sites. Combining all the sub-PMP solutions, a spatial voting strategy is introduced to select candidate facility sites to construct a PMP for obtaining the final problem solution. The RSSV algorithm is well-suited to the parallel structure of the HPC platform. Tests with the BIRCH dataset show that RSSV provides high-quality solutions and reduces computing time significantly. Tests also demonstrate the dynamic scalability of the algorithm; it can start with a small amount of computing resources and scale up or down when the availability of computing resources changes. Chapter 4 provides a new classification scheme to draw choropleth maps when data contain uncertainty. Considering that units in the same class on a choropleth map are assigned the same color or pattern, the new approach assumes the existence of a representative value for each class. A maximum likelihood estimation (MLE) based approach is developed to determine class breaks so that the overall within-class deviation is minimized while considering uncertainty. Different methods, including mixed integer programming, dynamic programming, and an interchange heuristic, are developed to solve the new classification problem. The proposed mapping approach is then applied to map two American Community Survey datasets. The effectiveness of the new approach is demonstrated, and the linkage of the approach with the PMP method and the Jenks Natural Breaks is discussed.

No description available.

This dissertation studies in depth the structure of the Discrete Ordered Median Problem (DOMP), to define new formulations and resolution algorithms. Furthermore we analyze an interesting extension for DOMP, namely MDOMP (Monotone Discrete Ordered Median Problem). This thesis is structured in three main parts.First, a widely theoretical and computational study is reported. It presents several new formulations for the Discrete Ordered Median Problem (DOMP) based on its similarity with some scheduling problems. Some of the new formulations present a considerably smaller number of constraints to define the problem with respect to some previously known formulations. Furthermore, the lower bounds provided by their linear relaxations improve the ones obtained with previous formulations in the literature even when strengthening is not applied. We also present a polyhedral study of the assignment polytope of our tightest formulation showing its proximity to the convex hull of the integer solutions of the problem. Several resolution approaches, among which we mention a branch and cut algorithm, are compared. Extensive computational results on two families of instances, namely randomly generated and from Beasley's OR-library, show the power of our methods for solving DOMP. One of the achievements of the new formulation consists in its tighter LP-bound. Secondly, DOMP is addressed with a new set partitioning formulation using an exponential number of variables. This chapter develops a new formulation in which each variable corresponds to a set of demand points allocated to the same facility with the information of the sorting position of their corresponding distances. We use a column generation approach to solve the continuous relaxation of this model. Then, we apply a branch-cut-and-price algorithm to solve to optimality small to moderate size of DOMP in competitive computational time.To finish, the third contribution of this dissertation is to analyze and compare formulations for the monotone discrete ordered median problem. These formulations combine different ways to represent ordered weighted averages of elements by using linear programs together with the p-median polytope. This approach gives rise to two efficient formulations for DOMP under a hypothesis of monotonicity in the lambda vectors. These formulations are theoretically compared and also compared with some other formulations valid for the case of general lambda vector. In addition, it is also developed another new formulation, for the general case, that exploits the efficiency of the rationale of monotonicity. This representation allows to solve very efficiently some DOMP instances where the monotonicity is only slightly lost. Detailed computational tests on all these formulations is reported in the dissertation. They show that specialized formulations allow to solve to optimality instances with sizes that are far beyond the limits of those that can solve in the general case. / Cette dissertation étudie en profondeur la structure du "Discrete Ordered Median Problem" (DOMP), afin de proposer de nouvelles formulations et de nouveaux algorithmes de résolution. De plus, une extension intéressante du DOMP nommée MDOMP ("Monotone Discrete Ordered Median Problem") a été étudiée.Cette thèse a été structurée en trois grandes parties.La première partie présente une étude riche aux niveaux théorique et expérimentale. Elle développe plusieurs formulations pour le DOMP qui sont basées sur des problèmes d'ordonnancement largement étudiés dans la littérature. Plusieurs d'entres elles nécessitent un nombre réduit de contraintes pour définir le problème en ce qui concerne certaines formulations connues antérieurement. Les bornes inférieures, qui sont obtenues par la résolution de la relaxation linéaire, donnent de meilleurs résultats que les formulations précédentes et ceci même avec tout processus de renforcement désactivé. S'ensuit une étude du polyhèdre de notre formulation la plus forte qui montre sa proximité entre l'enveloppe convexe des solutions entières de notre problème. Un algorithme de branch and cut et d'autres méthodes de résolution sont ensuite comparés. Les expérimentations qui montrent la puissance de nos méthodes s'appuient sur deux grandes familles d'instances. Les premières sont générées aléatoirement et les secondes proviennent de Beasley's OR-library. Ces expérimentations mettent en valeur la qualité de la borne obtenue par notre formulation.La seconde partie propose une formulation "set partitioning" avec un nombre exponentiel de variables. Dans ce chapitre, la formulation comporte des variables associées à un ensemble de demandes affectées à la même facilité selon l'ordre établi sur leurs distances correspondantes. Nous avons alors développé un algorithme de génération de colonnes pour la résolution de la relaxation continue de notre modèle mathématique. Cet algorithme est ensuite déployé au sein d'un Branch-and-Cut-and-Price afin de résoudre des instances de petites et moyennes tailles avec des temps compétitifs.La troisième partie présente l'analyse et la comparaison des différentes formulations du problème DOMP Monotone. Ces formulations combinent plusieurs manières de formuler l'ordre des éléments selon les moyennes pondérées en utilisant plusieurs programmes linéaires du polytope du p-median. Cette approche donne lieu à deux formulations performantes du DOMP sous l'hypothèse de monotonie des vecteurs lambda. Ces formulations sont comparées de manière théorique puis comparées à d'autres formulations valides pour le cas général du vecteur lambda. Une autre formulation est également proposée, elle exploite l'efficacité du caractère rationnel de la monotonie. Cette dernière permet de résoudre efficacement quelques instances où la monotonie a légèrement disparue. Ces formulations ont fait l'objet de plusieurs expérimentations dècrites dans ce manuscrit de thèse. Elles montrent que les formulations spécifiques permettent de résoudre des instances plus importantes que pour le cas général. / Este trabajo estudia en profundidad la estructura del problema disctreto de la mediana ordenada (DOMP, por su acrónimo en inglés) con el objetivo de definir nuevas formulaciones y algoritmos de resolución. Además, analizamos una interesante extensión del DOMP conocida como el problema monótono discreto de la mediana ordenada (MDOMP, de su acrónimo en inglés).Esta tesis se compone de tres grandes bloques.En primer lugar, se desarrolla un detallado estudio teórico y computacional. Se presentan varias formulaciones nuevas para el problema discreto de la mediana ordenada (DOMP) basadas en su similaridad con algunos problemas de secuenciación. Algunas de estas formulaciones requieren de un cosiderable menor número de restricciones para definir el problema respecto a algunas de las formulaciones previamente conocidas. Además, las cotas inferiores proporcionadas por las relajaciones lineales mejoran a las obtenidas con formulaciones previas de la literatura incluso sin reforzar la nueva formulación. También presentamos un estudio poliédrico del politopo de asignación de nuestra formulación más compacta mostrando su proximidad con la envolvente convexa de las soluciones enteras del problema. Se comparan algunos procedimientos de resolución, entre los que destacamos un algoritmo de ramificación y corte. Amplios resultados computacionales sobre dos familias de instancias -aleatoriamente generadas y utilizando la Beasley's OR-library- muestran la potencia de nuestros métodos para resolver el DOMP.En el segundo bloque, el problema discreto de la mediana ordenada es abordado con una formulación de particiones de conjuntos empleando un número exponencial de variables. Este capítulo desarrolla una nueva formulación en la que cada variable corresponde a un conjunto de puntos de demanda asignados al mismo servidor con la información de la posición obtenida de ordenar las distancias correspondientes. Utilizamos generación de columnas para resolver la relajación continua del modelo. Después, empleamos un algoritmo de ramificación, acotación y "pricing" para resolver a optimalidad tamaños moderados del DOMP en un tiempo computacional competitivo.Por último, el tercer bloque de este trabajo se dedica a analizar y comparar formulaciones para el problema monótono discreto de la mediana ordenada. Estas formulaciones combinan diferentes maneras de representar medidas de pesos ordenados de elementos utilizando programación lineal junto con el politopo de la $p$-mediana. Este enfoque da lugar a dos formulaciones eficientes para el DOMP bajo la hipótesis de monotonía en su vector $lambda$. Se comparan teóricamente las formulaciones entre sí y frente a algunas de las formulaciones válidas para el caso general. Adicionalmente, se desarrolla otra formulación válida para el caso general que explota la eficiencia de las ideas de la monotonicidad. Esta representación permite resolver eficientemente algunos ejemplos donde la monotonía se pierde ligeramente. Finalmente, llevamos a cabo un detallado estudio computacional, en el que se aprecia que las formulaciones ad hoc permiten resolver a optimalidad ejemplos cuyo tamaño supera los límites marcados en al caso general. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

This dissertation presents spatial partitioning algorithms to solve location-allocation problems. Location-allocations problems pertain to both the selection of facilities to serve demand at demand points and the assignment of demand points to the selected or known facilities. In the first part of this dissertation, we focus on the well known and well-researched location-allocation problem, the "p-median problem", which is a distance-based location-allocation problem that involves selection and allocation of p facilities for n demand points. We evaluate the performance of existing p-median heuristic algorithms and investigate the impact of the scale of the problem, and the spatial distribution of demand points on the performance of these algorithms. Based on the results from this comparative study, we present guidelines for location analysts to aid them in selecting the best heuristic and corresponding parameters depending on the problem at hand. Additionally, we found that existing heuristic algorithms are not suitable for solving large-scale p-median problems in a reasonable amount of time. We present a density-based decomposition methodology to solve large-scale p-median problems efficiently. This algorithm identifies dense clusters in the region and uses a MapReduce procedure to select facilities in the clustered regions independently and combine the solutions from the subproblems. Lastly, we present a novel greedy heuristic algorithm to solve the contiguity constrained fixed facility demand distribution problem. The objective of this problem is to create contiguous service areas for the facilities such that the demand at all facilities is uniform or proportional to the available resources, while the distance between demand points and facilities is minimized. The results in this research are shown in the context of creating emergency response plans for bio-emergencies. The algorithms are used to select Point of Dispensing (POD) locations (if not known) and map them to population regions to ensure that all affected individuals are assigned to a POD facility.

This research is concerned with the development of algorithmic approaches for solving problems that arise in the design and analysis of telecommunication networks, location-allocation distribution contexts, and intelligent transportation networks. Specifically, the corresponding problems addressed in these areas are a local access and transport area (LATA) network design problem, the discrete equal-capacity p-median problem (PMED), and the estimation of dynamic origin-destination path ows or trip tables in a general network. For the LATA network problem, we develop a model and apply the Reformulation-Linearization Technique (RLT) to construct various enhanced tightened versions of the proposed model. We also design efficient Lagrangian dual schemes for solving the linear programming relaxation of the various enhanced models, and construct an effective heuristic procedure for deriving good quality solutions in this process. Extensive computational results are provided to demonstrate the progressive tightness resulting from the enhanced formulations and their effect on providing good quality feasible solutions. The results indicate that the proposed procedures typically yield solutions having an optimality gap of less than 2% with respect to the derived lower bound, within a reasonable effort that involves the solution of a single linear program. For the discrete equal-capacity p-median problem, we develop various valid inequalities, a separation routine for generating cutting planes via specific members of such inequalities, as well as an enhanced reformulation that constructs a partial convex hull representation that subsumes an entire class of valid inequalities via its linear programming relaxation. We also propose suitable heuristic schemes for solving this problem, based on sequentially rounding the continuous relaxation solutions obtained for the various equivalent formulations of the problem. Extensive computational results are provided to demonstrate the effectiveness of the proposed valid inequalities, enhanced formulations, and heuristic schemes. The results indicate that the proposed schemes for tightening the underlying relaxations play a significant role in enhancing the performance of both exact and heuristic solution methods for solving this class of problems. For the estimation of dynamic path ows in a general network, we propose a parametric optimization approach to estimate time-dependent path ows, or origin-destination trip tables, using available data on link traffic volumes for a general road network. Our model assumes knowledge of certain time-dependent link ow contribution factors that are a dynamic generalization of the path-link incidence matrix for the static case. We propose a column generation approach that uses a sequence of dynamic shortest path subproblems in order to solve this problem. Computational results are presented on several variants of two sample test networks from the literature. These results indicate the viability of the proposed approach for use in an on-line mode in practice. Finally, we present a summary of our developments and results, and offer several related recommendations for future research. / Ph. D.