Explore the vast range of titles available.

Spanning tree problems with specialized constraints can be difficult to solve in real-world scenarios, often requiring intricate algorithmic design and exponential time. Recently, there has been growing interest in end-to-end deep neural networks for solving routing problems. However, such methods typically produce sequences of vertices, which make it difficult to apply them to general combinatorial optimization problems where the solution set consists of edges, as in various spanning tree problems. In this paper, we propose NeuroPrim, a novel framework for solving various spanning tree problems by defining a Markov decision process for general combinatorial optimization problems on graphs. Our approach reduces the action and state space using Prim’s algorithm and trains the resulting model using REINFORCE. We apply our framework to three difficult problems on the Euclidean space: the degree-constrained minimum spanning tree problem, the minimum routing cost spanning tree problem and the Steiner tree problem in graphs. Experimental results on literature instances demonstrate that our model outperforms strong heuristics and achieves small optimality gaps of up to 250 vertices. Additionally, we find that our model has strong generalization ability with no significant degradation observed on problem instances as large as 1,000. Our results suggest that our framework can be effective for solving a wide range of combinatorial optimization problems beyond spanning tree problems.

In this study, the authors envisage the neutrosophic number from various distinct rational perspectives and viewpoints to give it a look of a conundrum. They focused and analysed neutrosophic fuzzy numbers when indeterminacy and falsity functions are dependent on each other, which serves an indispensable role for the uncertainty concept. Additionally, the idea of cylindrical neutrosophic single-valued number is focused here, when the indeterminacy and falsity functions are dependent to each other using an influx of different logical and innovative graphical representation. They also developed the score and accuracy function for this particular cylindrical neutrosophic single-valued number and analysed some real-life problems like networking critical path model problem and minimal spanning tree problem of operation research field when the numbers are in cylindrical neutrosophic ambiance. They also introduced a multi-criterion group decision-making problem in this cylindrical neutrosophic domain. This noble thought will help us to solve a plethora of daily life problems in the neutrosophic arena.

In this survey paper, we discuss the development of the Generalized Minimum Spanning Tree Problem, denoted by GMSTP, and we focus on the integer programming formulations of the problem. The GMSTP is a variant of the classical minimum spanning tree problem (MST), in which the nodes of an undirected graph are partitioned into node sets (clusters) and we are looking for a minimum cost tree spanning a subset of nodes which includes exactly one node from every cluster. In this paper we describe twelve distinct formulations of the GMSTP based on integer programming. Apart from the standard formulations all the new formulations that we describe are 'compact' in the sense that the number of constraints and variables is a polynomial function of the number of nodes in the problem. Comparisons of the poly topes corresponding to their linear relaxations are established.

In real path selection decisions, besides the cost of the path which is the major decision factor, the chance of the path connection is also significant. A path which has low weight but low chance of existence is not a good choice for decision-making. In order to make network optimization more in line with the actual situation, this paper studies one model of it on a network whose existence and weight of edges are both indeterminate. The aim of this paper is to obtain a spanning tree which satisfies the connectivity constraint and minimizes the total weight as well. The study uses conditional uncertain variable to describe the relationship between these two aspects of uncertain variables. On this basis, three different models of the UMST problem are suggested, and the equivalence relation between the MST model of uncertain networks with uncertain edge existence and weight and the MST of related deterministic networks is found. Examples of experiments with specific numerical values are provided to verify the variation in the network when two variables are considered simultaneously.

Minimum spanning tree problem (MSTP) has allured many researchers and practitioners due to its varied range of applications in real world scenarios. Modelling these applications involves the incorporation of indeterminate phenomena based on their subjective estimations. Such phenomena can be represented rationally using uncertainty theory. Being a more realistic variant of MSTP, in this article, based on the principles of the uncertainty theory, we have studied a multi-objective minimum spanning tree problem (MMSTP) with indeterminate problem parameters. Subsequently, two uncertain programming models of the proposed uncertain multi-objective minimum spanning tree problem (UMMSTP) are developed and their corresponding crisp equivalence models are investigated, and eventually solved using a classical multi-objective solution technique, the epsilon-constraint method. Additionally, two multi-objective evolutionary algorithms (MOEAs), non-dominated sorting genetic algorithm II (NSGAII) and duplicate elimination non-dominated sorting evolutionary algorithm (DENSEA) are also employed as solution methodologies. With the help of the proposed UMMSTP models, the practical problem of optimizing the distribution of petroleum products was solved, consisting in the search for symmetry (balance) between the transportation cost and the transportation time. Thereafter, the performance of the MOEAs is analyzed on five randomly developed instances of the proposed problem.

The quadratic minimum spanning tree problem (QMSTP) is a spanning tree optimization problem that considers the interaction cost between pairs of edges arising from a number of practical scenarios. This problem is NP-hard, and therefore there is not a known polynomial time approach to solve it. To find a close-to-optimal solution to the problem in a reasonable time, we present for the first time a clustering-enhanced memetic algorithm (CMA) that combines four components, i.e., (i) population initialization with clustering mechanism, (ii) a tabu-based nearby exploration phase to search nearby local optima in a restricted area, (iii) a three-parent combination operator to generate promising offspring solutions, and (iv) a mutation operator using Lévy distribution to prevent the population from premature. Computational experiments are carried on 36 benchmark instances from 3 standard sets, and the results show that the proposed algorithm is competitive with the state-of-the-art approaches. In particular, it reports improved upper bounds for the 25 most challenging instances with unproven optimal solutions, while matching the best-known results for all but 2 of the remaining instances. Additional analysis highlights the contribution of the clustering mechanism and combination operator to the performance of the algorithm.

In recent years, with the variety of digital objects around us becoming a source of information, the fields of artificial intelligence (AI) and machine learning (ML) have experienced very rapid development. Processing and converting the information around us into data within the framework of the information processing theory is important, as AI and ML techniques need large amounts of reliable data in the training and validation stages. Even though information naturally contains uncertainty, information must still be modeled and converted into data without neglecting this uncertainty. Mathematical techniques, such as the fuzzy theory and the intuitionistic fuzzy theory, are used for this purpose. In the intuitionistic fuzzy theory, membership and non-membership functions are employed to describe intuitionistic fuzzy sets and intuitionistic fuzzy numbers (IFNs). IFNs are characterized by the mathematical statements of these two functions. A more general and inclusive definition of IFN is always a requirement in AI technologies, as the uncertainty introduced by various information sources needs to be transformed into similar IFNs without neglecting the variety of uncertainty. In this paper, we proposed a general and inclusive mathematical definition for IFN and called this IFN a non-linear pentagonal intuitionistic fuzzy number (NLPIFN), which allows its users to maintain variety in uncertainty. We know that AI technology implementations are performed in computerized environments, so we need to transform the IFN into a crisp number to make such IFNs available in such environments. Techniques used in transformation are called defuzzification methods. In this paper, we proposed a short-cut formula for the defuzzification of a NLPIFN using the intuitionistic fuzzy weighted averaging based on levels (IF-WABL) method. We also implemented our findings in the minimum spanning tree problem by taking weights as NLPIFNs to determine the uncertainty in the process more precisely.

Capacitated Minimum Spanning Tree Problem (CMSTP), a well-known combinatorial optimization problem, holds the central place in telecommunication network design. This problem involves finding a minimum cost spanning tree with an extra cardinality limitation on the orders of the subtrees incident to a certain root node. The Balanced Capacitated Minimum Spanning Tree Problem (BCMSTP) is a special case that aims to balance the orders of the subtrees. This problem is an NP-hard one and presents two approximation algorithms in this paper. By considering the maximum order of the subtrees Q, a (3 - 1/Q)-approximation algorithm was provided to find a balanced solution. This result was improved to a (2.5 + ε) approximation algorithm (for every given ε > 0) in the 2d-Euclidean spaces. Also, a Polynomial Time Approximation Scheme (PTAS) was presented for CMSTP.

This paper develops a greedy heuristic for the capacitated minimum spanning tree problem (CMSTP), based on the two widely known methods of Prim and of Esau–Williams. The proposed algorithm intertwines two-stages: an enhanced combination of the Prim and Esau–Williams approaches via augmented and synthetic node selection criteria, and an increase of the feasible solution space by perturbing the input data using the law of cosines. Computational tests on benchmark problems show that the new heuristic provides extremely good performance results for the CMSTP, justifying its effectiveness and robustness. Furthermore, excluding the feasible space expansion, we show that we can still obtain good quality solutions in very short computational times.

Given a connected undirected graph G whose edges are labeled, the minimum labeling spanning tree (MLST) problem is to find a spanning tree of G with the smallest number of different labels. The MLST is an NP-hard combinatorial optimization problem, which is widely applied in communication networks, multimodal transportation networks, and data compression. Some approximation algorithms and heuristics algorithms have been proposed for the problem. Firefly algorithm is a new meta-heuristic algorithm. Because of its simplicity and easy implementation, it has been successfully applied in various elds. However, the basic firefly algorithm is not suitable for discrete problems. To this end, a novel discrete firefly algorithm for the MLST problem is proposed in this paper. A binary operation method to update firefly positions and a local feasible handling method are introduced, which correct unfeasible solutions, eliminate redundant labels, and make the algorithm more suitable for discrete problems. Computational results show that the algorithm has good performance. The algorithm can be extended to solve other discrete optimization problems.