1,720,957 research outputs found
Una variación del problema de ordenamiento lineal
No full textEl objetivo de esta tesis es desarrollar un algoritmo exacto para una variante del problema de ordenamiento lineal basado en un modelo de programación lineal entera. El problema de ordenamiento lineal es un problema clásico de optimización combinatoria estudiado desde hace más de 50 años. Los diversos escenarios reales que provienen de situaciones surgidas en variados campos de la industria y otros sectores, han dado origen a distintas variaciones de este problema. La gran cantidad de aplicaciones que poseen los problemas de esta familia hacen que los mismos no solo tengan interés teórico, sino también, una gran importancia práctica. La versión del problema abordada en este trabajo consiste en encontrar un orden total de elementos de manera que se minimice la suma de las penalidades entre pares de ellos, donde la penalidad se define como el producto entre la distancia a la que se encuentran los dos elementos y un costo asociado a ellos. Este problema recibe el nombre de Problema de Ordenamiento Lineal con Penalidades POLP. POLP pertenece a la clase de problemas NP-Difícil. Para estos problemas no se conocen algoritmos que encuentren la solución en tiempo polinomial. Como muchos de los problemas de Optimización Combinatoria, POLP puede ser modelado mediante formulaciones de programación lineal entera o entera mixta. Los algoritmos Branch-and-Cut son una de las herramientas más efectivas que se conoce para resolver un modelo de programación lineal entera. Especialmente las implementaciones basadas en combinatoria poliedral han permitido incrementar el tamaño de las instancias resueltas. En el transcurso del trabajo se analizan diversas formulaciones de programación lineal entera que permiten modelar el problema. Luego de seleccionar la más prometedora según ciertos criterios, se realiza un estudio poliedral para determinar características de la cápsula convexa del conjunto de soluciones factibles. En base a estas familias de desigualdades válidas, se desarrolló e implementó un algoritmo Branch-and-Cut para resolver el problema. También se consideraron factores decisivos en la eficiencia de este tipo de algoritmos, como la incorporación de heurísticas iniciales y primales, distintas estrategias de selección de variable de branching, y esquemas de recorrido del árbol de Branch-and-Bound. Finalmente se muestran resultados experimentales sobre instancias de prueba que permiten evaluar la eficiencia del algoritmo desarrollado.Fil: Curcio, Brian Luis. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina
Problems on vertex distinguishing edge colorings
Get PDFEn el presente trabajo analizamos el problema de suma de coloreo de aristas con vértices adyacentes distinguibles. Un coloreo de aristas con vértices adyacentes distinguibles es una asignación de colores a las aristas de un grafo con las siguientes restricciones: todo par de aristas adyacentes debe tener distinto color, y todo par de vértices adyacentes debe tener diferencia en el conjunto de colores asignados a sus aristas incidentes. El objetivo es minimizar la suma de los colores asignados en un coloreo de aristas que cumpla estas restricciones. Este problema es un caso particular de una gran familia de problemas conocida bajo el nombre de etiquetado de grafos, que resultan una herramienta abstracta muy útil y versátil para modelar situaciones de la vida cotidiana que se quieren formalizar y resolver mediante algoritmos. Algunas variantes del problema de etiquetado de grafos han sido abordadas con éxito con técnicas de programación lineal entera basadas en la caracterización poliedral del conjunto de soluciones factibles. Bajo este enfoque, en esta tesis nos proponemos desarrollar un algoritmo tipo Branch and Cut para resolver el problema. Además, aprovechando el análisis realizado, también hacemos una propuesta algorítmica para resolver el problema que busca minimizar la cantidad de colores utilizados en el coloreo. Adicionalmente, se exploró la opción de utilizar técnicas heurísticas para resolver el problema. Las heurísticas permiten conocer asignaciones de colores factibles del problema pero, en general, no pueden determinar si son óptimas o cuan cerca están de la solución del problema. Desarrollamos tres técnicas distintas para resolver el problema: un algoritmo goloso, un algoritmo de programación por restricciones, y un algoritmo de generación de columnas. Para el desarrollo del algoritmo tipo Branch and Cut, propusimos dos modelos de programación lineal entera que evaluamos empíricamente para elegir el más prometedor, sobre el cual se realizó un estudio poliedral en profundidad. Caracterizamos la dimensión del poliedro asociado y demostramos que tres familias de desigualdades válidas definen facetas. El objetivo de realizar el estudio poliedral es entender mejor el espacio de soluciones del modelo para conseguir formulaciones más ajustadas que mejoren la performance del algoritmo. Las desigualdades estudiadas son incorporadas como cortes al modelo, para las cuales se desarrollaron algoritmos de separación que permiten agregarlas a demanda. Además, se consideraron heurística inicial, preprocesamiento y estrategias particulares de generación del árbol de búsqueda. Los resultados muestran que el algoritmo desarrollado permite resolver instancias que no son posibles de abordar utilizando las herramientas de resolución generales. Haber realizado el estudio poliedral y agregar las facetas como planos de corte resulta ser un factor determinante para afrontar instancias del problema mucho más desafiantes.In this thesis we analyze the adjacent vertex distinguishing sum edge coloring problem. This problem consists in finding an assignment of colors to the edges of a graph with the following constraints: every pair of adjacent edges must have a different color, and every pair of adjacent vertices must not have the same set of colors assigned to the edges incident to each. The goal is to minimize the sum of the colors in an edge coloring that satisfies these constraints. This problem is a special case of a large family of problems known as graph labeling, which are a widely used and very popular set of tools to build abstract models for problems that come up in everyday life. Some variants of graph labeling problem have been successfully addressed with mixed integer linear programming (MIP) techniques based on a polyhedral characterization of the set of feasible solutions. We use this approach to develop a branch and cut algorithm to solve the problem. Furthermore, taking advantage of the analysis, we also propose an algorithm to solve the problem that minimizes the number of colors used for an adjacent vertex distinguishing edge coloring. Additionally, we explored using heuristic techniques to solve the problem. These heuristics allow to obtain feasible coloring assignments for the problem but, in general, can not determine if they are optimal or even how far they are from the solution to the problem. We use three different approaches: a greedy algorithm, a constraint programming model and a column generation algorithm. To develop the branch and cut algorithm we propose two MIP models. We evaluate these models to choose the most promising one and continue with a thorough polyhedral study. We characterized the dimension of the associated polyhedron and proved that three families of valid inequalities result facet-inducing. The aim of the polyhedral study is to understand the set of feasible solutions in the model to obtain a more compact formulation in hope of improving the algorithm's performance. These inequalities are added as cutting planes in the model, we developed exact and heuristic separation algorithms to add them on demand. Moreover, we considered the use of initial heuristics, preprocessing and particular branching strategies. The results show that the algorithm developed allows us to solve instances that were unsolvable using general purpose solvers. Our polyhedral study and the addition of facets as cutting planes proved to be a crucial factor to solve the most challenging instances.Fil: Curcio, Brian Luis. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina
Problems on vertex distinguishing edge colorings
No full textEn el presente trabajo analizamos el problema de suma de coloreo de aristas con vértices adyacentes distinguibles. Un coloreo de aristas con vértices adyacentes distinguibles es una asignación de colores a las aristas de un grafo con las siguientes restricciones: todo par de aristas adyacentes debe tener distinto color, y todo par de vértices adyacentes debe tener diferencia en el conjunto de colores asignados a sus aristas incidentes. El objetivo es minimizar la suma de los colores asignados en un coloreo de aristas que cumpla estas restricciones. Este problema es un caso particular de una gran familia de problemas conocida bajo el nombre de etiquetado de grafos, que resultan una herramienta abstracta muy útil y versátil para modelar situaciones de la vida cotidiana que se quieren formalizar y resolver mediante algoritmos. Algunas variantes del problema de etiquetado de grafos han sido abordadas con éxito con técnicas de programación lineal entera basadas en la caracterización poliedral del conjunto de soluciones factibles. Bajo este enfoque, en esta tesis nos proponemos desarrollar un algoritmo tipo Branch and Cut para resolver el problema. Además, aprovechando el análisis realizado, también hacemos una propuesta algorítmica para resolver el problema que busca minimizar la cantidad de colores utilizados en el coloreo. Adicionalmente, se exploró la opción de utilizar técnicas heurísticas para resolver el problema. Las heurísticas permiten conocer asignaciones de colores factibles del problema pero, en general, no pueden determinar si son óptimas o cuan cerca están de la solución del problema. Desarrollamos tres técnicas distintas para resolver el problema: un algoritmo goloso, un algoritmo de programación por restricciones, y un algoritmo de generación de columnas. Para el desarrollo del algoritmo tipo Branch and Cut, propusimos dos modelos de programación lineal entera que evaluamos empíricamente para elegir el más prometedor, sobre el cual se realizó un estudio poliedral en profundidad. Caracterizamos la dimensión del poliedro asociado y demostramos que tres familias de desigualdades válidas definen facetas. El objetivo de realizar el estudio poliedral es entender mejor el espacio de soluciones del modelo para conseguir formulaciones más ajustadas que mejoren la performance del algoritmo. Las desigualdades estudiadas son incorporadas como cortes al modelo, para las cuales se desarrollaron algoritmos de separación que permiten agregarlas a demanda. Además, se consideraron heurística inicial, preprocesamiento y estrategias particulares de generación del árbol de búsqueda. Los resultados muestran que el algoritmo desarrollado permite resolver instancias que no son posibles de abordar utilizando las herramientas de resolución generales. Haber realizado el estudio poliedral y agregar las facetas como planos de corte resulta ser un factor determinante para afrontar instancias del problema mucho más desafiantes.In this thesis we analyze the adjacent vertex distinguishing sum edge coloring problem. This problem consists in finding an assignment of colors to the edges of a graph with the following constraints: every pair of adjacent edges must have a different color, and every pair of adjacent vertices must not have the same set of colors assigned to the edges incident to each. The goal is to minimize the sum of the colors in an edge coloring that satisfies these constraints. This problem is a special case of a large family of problems known as graph labeling, which are a widely used and very popular set of tools to build abstract models for problems that come up in everyday life. Some variants of graph labeling problem have been successfully addressed with mixed integer linear programming (MIP) techniques based on a polyhedral characterization of the set of feasible solutions. We use this approach to develop a branch and cut algorithm to solve the problem. Furthermore, taking advantage of the analysis, we also propose an algorithm to solve the problem that minimizes the number of colors used for an adjacent vertex distinguishing edge coloring. Additionally, we explored using heuristic techniques to solve the problem. These heuristics allow to obtain feasible coloring assignments for the problem but, in general, can not determine if they are optimal or even how far they are from the solution to the problem. We use three different approaches: a greedy algorithm, a constraint programming model and a column generation algorithm. To develop the branch and cut algorithm we propose two MIP models. We evaluate these models to choose the most promising one and continue with a thorough polyhedral study. We characterized the dimension of the associated polyhedron and proved that three families of valid inequalities result facet-inducing. The aim of the polyhedral study is to understand the set of feasible solutions in the model to obtain a more compact formulation in hope of improving the algorithm's performance. These inequalities are added as cutting planes in the model, we developed exact and heuristic separation algorithms to add them on demand. Moreover, we considered the use of initial heuristics, preprocessing and particular branching strategies. The results show that the algorithm developed allows us to solve instances that were unsolvable using general purpose solvers. Our polyhedral study and the addition of facets as cutting planes proved to be a crucial factor to solve the most challenging instances.Fil: Curcio, Brian Luis. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Get PDF“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Get PDFWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
Dispelling the Myths Behind First-author Citation Counts
Get PDFWe conducted a full-scale evaluative citation analysis study of scholars in the XML research field to explore just how different from each other author rankings resulting from different citation counting methods actually are, and to demonstrate the capability of emerging data and tools on the Web in supporting more realistic citation counting methods. Our results contest some common arguments for the continued
use of first-author citation counts in the evaluation of scholars, such as high correlations between author rankings by first-author citation counts and other citation
counting methods, and high costs of using more realistic citation counting methods that are not well-supported by the ISI databases. It is argued that increasingly available digital full text research papers make it possible for citation analysis studies to go beyond what the ISI databases have directly supported and to employ more
sophisticated methods
A cluster-first route-second approach for the swap body vehicle routing problem
Get PDFThe swap body vehicle routing problem (SB-VRP) is a generalization of the classical vehicle routing problem where a particular structure as well as several operational aspects for the trucks composing the fleet are considered. This research has been motivated by the VeRoLog Solver Challenge 2014, organized together by VeRoLog and PTV group, aiming to motivate the study of real-world logistic problems. A truck can carry either only one swap body or, in addition, an extra trailer with an extra swap body. For the latter, special depots, called swap locations, can be used to drop and pickup the swap bodies. These operations may affect the feasibility and the cost of a route, and therefore the overall operational cost. In this paper, we propose a cluster-first route-second heuristic for the SB-VRP. Computational experiments are conducted over the benchmark instances proposed for the competition, simulating a practical environment by considering limited resources and execution time. The results obtained are of very good quality, where our approach ended as runner-up in the final set of instances and performs similarly to the other algorithms in the remaining cases, showing its potential to be applied in practice.Fil: Miranda Bront, Juan Jose. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; ArgentinaFil: Curcio, Brian Luis. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; ArgentinaFil: Méndez-Díaz, Isabel. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; ArgentinaFil: Montero, Agustin Ismael. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; ArgentinaFil: Pousa, Federico Javier. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; ArgentinaFil: Zabala, Paula Lorena. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentin
- …
