1,720,957 research outputs found
Gelişigüzel düğüm dağılımlarına sahip GSP örneklerinin en iyi tur uzunluğunu tahminlemek için sinir ağı tahminleyicileri
No full textTo achieve operational efficiency in logistics, we need to solve complex routing problems. Due to their complexity, these problems are often solved sequentially, i.e., using cluster-first route-second (CFRS) type frameworks. However, such two-phase frameworks generally suffer from sub-optimality arising from the first phase. To mitigate this sub-optimality, information about optimal tour lengths of potential clusters can be exploited first, thereby transforming this two-phase approach into a less myopic solution framework. In that aspect, a quick and highly accurate Traveling Salesperson Problem (TSP) tour length estimator can be utilized for searching high-quality clusters. Motivated by this, we propose novel and computationally efficient neural network-based optimal TSP tour length estimators. Our approach uses an entirely new feature set consisting of node level, instance level, and solution level features by combining the power of artificial neural networks and theoretical knowledge in the routing domain. This data and knowledge hybridization enables us to achieve predictions with less than 0.7 percent deviation (on average) from the optimality. Unlike previous studies, we design and use new instances mimicking real-life logistics networks and morphologies. These instance characteristics introduce a substantial computational cost, making our instances harder to solve. To cope with these pathologies, we devise a new and efficient way of finding lower bounds and partial solutions to TSP later to be used as solution-level predictors. We also conduct a computational study where we produce up to 100 times lower prediction error on out-of-distribution test instances. Finally, we develop an enumeration-like mechanism by incorporating proposed machine learning models and metaheuristics to solve massive-scale rout- ing problems efficiently. We significantly outperform the state-of-the-art solver in terms of solution time and quality, demonstrating the potential of our models and the proposed method.Lojistikte operasyonel verimlilik için, karmaşık rotalama problemlerini çözmeye ihtiyaç duymaktayız. Bu problemlerin karmaşıklığından kaynaklı olarak, genelde önce-kümele sonra-rotala (ÖKSR) benzeri sıralı çözüm yöntemleri kullanılmaktadır. Fakat, bu tip iki fazlı çözüm yöntemlerinden elde edilen sonuçlar genelde alt-optimallikten muzdarip olmaktadır. Buradaki alt-optimalliği azaltmak adına, yaratılan kümelere ait optimal tur uzunlukları bilgilerinden faydalanılabilir. Bu sayede, bahsedilen iki fazlı çözüm yöntemi daha az miyopik bir çözüm yöntemine dönüştürülmüş olur. Bu bakımdan, çabuk ve yüksek isabetli bir Gezgin Satıcı Problemi (GSP) tur uzunluğu tahminleyicisi yüksek kaliteli kümeleri aramak amacıyla kullanılabilir. Buradan yola çıkarak, yeni ve hesaplama bakımından verimli, yapay sinir ağı temelli optimal GSP tur uzunluğu tahminleyicileri öneriyoruz. Yaklaşımımız, yapay sinir ağlarının gücünü rotalama alanındaki teorik bilgi ile birleştirerek düğüm seviyesi, örnek seviyesi ve çözüm seviyesi özniteliklerinden oluşan tamamen yeni bir öznitelik seti kullanmaktadır. Bu veri ve alan bilgisi hibridizasyonu, yüzde 0.7'den (ortalamada) daha az sapma ile en iyi tur uzunluğu tahminlemesine olanak sağlamaktadır. Önceki çalışmalardan farklı olarak, gerçek dünya lojistik ağ ve morfolojilerini örnek alan yeni tip örnekler tasarlayıp kullanıyoruz. Bu yeni tip örneklerin bazı karakteristik özellikleri hesaplama bakımından ciddi maliyetleri beraberinde getirerek optimal çözümlerin elde edilmesini zorlaştırmaktadır. Bu tip problem patolojileri ile başa çıkmak adına optimal GSP çözümüne ait daha sonra çözüm seviyesinde öznitelikler olarak kullanmak üzere alt sınır ve kısmi çözümler bulan yeni ve verimli bir yöntem geliştiriyoruz. Ek olarak, en iyi makine öğrenmesi modellerine göre dağılım dışı problem örneklerinde 100 kata kadar daha az tahminsel hata yaptığımızı gösteren bir hesaplamalı çalışma yapıyoruz. Son olarak, önerilen makine öğrenmesi modellerini metasezgisel yöntemlerle birleştirerek çok büyük rotalama problemlerini etkili bir şekilde numaralandırma benzeri bir mekanizma ile çözülmesini sağlayan yöntem geliştiriyoruz. Geliştirilen yöntem en gelişmiş çözücüye kıyasla hem çözüm kalitesi hem de çözüm süresi bakımından ciddi şekilde daha iyi performans göstererek önerilen modellerin ve önerilen yöntemlerin potansiyellerini ortaya koymaktadır
Neural network estimators for optimal tour lengths of traveling salesperson problem instances with arbitrary node distributions
No full textIt is essential to solve complex routing problems to achieve operational efficiency in logistics. However, because of their complexity, these problems are often tackled sequentially using cluster-first, route-second frameworks. Unfortunately, such two-phase frameworks can suffer from suboptimality due to the initial phase. To address this issue, we propose leveraging information about the optimal tour lengths of potential clusters as a preliminary step, transforming the two-phase approach into a less myopic solution framework. We introduce quick and highly accurate Traveling Salesperson Problem (TSP) tour length estimators based on neural networks (NNs) to facilitate this. Our approach combines the power of NNs and theoretical knowledge in the routing domain, utilizing a novel feature set that includes node-level, instance-level, and solution-level features. This hybridization of data and domain knowledge allows us to achieve predictions with an average deviation of less than 0.7% from optimality. Unlike previous studies, we design and employ new instances replicating real-life logistics networks and morphologies. These instances possess characteristics that introduce significant computational costs, making them more challenging. To address these challenges, we develop a novel and efficient method for obtaining lower bounds and partial solutions to the TSP, which are subsequently utilized as solution-level predictors. Our computational study demonstrates a prediction error up to six times lower than the best machine learning (ML) methods on their training instances and up to 100 times lower prediction error on out-of-distribution test instances. Furthermore, we integrate our proposed ML models with metaheuristics to create an enumeration-like solution framework, enabling the improved solution of massive scale routing problems. In terms of solution time and quality, our approach significantly outperforms the state-of-the-art solver, demonstrating the potential of our features, models, and the proposed method
Scalable primal heuristics using graph neural networks for combinatorial optimization
No full textBy examining the patterns of solutions obtained for various instances, one can gain insights into the structure and behavior of combinatorial optimization (CO) problems and develop efficient algorithms for solving them. Machine learning techniques, especially Graph Neural Networks (GNNs), have shown promise in parametrizing and automating this laborious design process. The inductive bias of GNNs allows for learning solutions to mixed-integer programming (MIP) formulations of constrained CO problems with a relational representation of decision variables and constraints. The trained GNNs can be leveraged with primal heuristics to construct high-quality feasible solutions to CO problems quickly. However, current GNN-based end -to -end learning approaches have limitations for scalable training and generalization on larger-scale instances; therefore, they have been mostly evaluated over small-scale instances. Addressing this issue, our study builds on sup ervised learning of optimal solutions to the downscaled instances of given large-scale CO problems. We introduce several improvements on a recent GNN model for CO to generalize on instances of a larger scale than those used in training. We also propose a two-stage primal heuristic strategy based on uncertainty-quantification to automatically configure how solution search relies on the predicted decision values. Our models can generalize on 16x upscaled instances of commonly benchmarked five CO problems. Unlike the regressive performance of existing GNN-based CO approaches as the scale of problems increases, the CO pipelines using our models offer an incremental performance improvement relative to CPLEX. The proposed uncertainty-based primal heuristics provide 6-75% better optimality gap values and 45-99% better primal gap values for the 16x upscaled instances and brings immense speedup to obtain high-quality solutions. All these gains are achieved through a computationally efficient modeling approach without sacrificing solution quality.TÜBİTA
Parallelization of genetic algorithms for software architecture recovery
No full textSoftware Architecture Recovery (SAR) techniques analyze dependencies between software modules and automatically cluster them to achieve high modularity. Many of these approaches employ Genetic Algorithms (GAs) for clustering software modules. A major drawback of these algorithms is their lack of scalability. In this paper, we address this drawback by introducing generic software components that can encapsulate subroutines (operators) of a GA to execute them in parallel. We use these components to implement a novel hybrid GA for SAR that exploits parallelism to find better solutions faster. We compare the effectiveness of parallel algorithms with respect to the sequential counterparts that are previously proposed for SAR. We observe that parallelization enables a greater number of iterations to be performed in the search for high-quality solutions. The increased efficiency achieved through parallel processing allows for faster convergence towards optimal solutions by harnessing the power of multiple processing units in a coordinated manner. The amount of improvement in modularity is above 50%, which particularly increases in the context of large-scale systems. Our algorithm can scale to recover the architecture of a large system, Chromium, which has more than 18,500 modules and 750,000 dependencies among these modules.TÜBİTA
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
- …
