Redundancy design is a widely used technique for enhancing system reliability across various industries, including aerospace and manufacturing. Consequently, the redundancy allocation problem (RAP) has attracted consi...
详细信息
Redundancy design is a widely used technique for enhancing system reliability across various industries, including aerospace and manufacturing. Consequently, the redundancy allocation problem (RAP) has attracted considerable attention in the field of reliability engineering. The RAP seeks to determine an optimal redundancy scheme for each subsystem under resource constraints to maximize system reliability. However, existing RAP models and exact algorithms are predominantly confined to simple 1-out-of-n subsystems or single optimization strategies, thereby limiting the optimization potential and failing to adequately address the engineering requirements. This paper introduces a model and an exact algorithm for RAP with k-out-of-n subsystems and heterogeneous components under mixed and K-mixed redundancy strategies. The model employs a continuous time Markov chain method to calculate subsystem reliability exactly. A dynamic programming (DP) algorithm based on super component and sparse node strategies is designed to obtain the exact solution for RAP. Numerical experiments confirm that all benchmark test problems reported in the literature are exactly solved by the proposed DP. The experiment results demonstrate that the proposed RAP model offers high flexibility and potential for reliability optimization. Additionally, owing to the generality of the problem considered, the proposed DP also exactly solves other RAP models with 1-out-of-n subsystems and simplified redundancy strategies, which provides a more generalized framework for redundancy optimization. Finally, the research's applicability in reliability engineering is validated through an optimization case study of a natural gas compressor pipeline system.
The Closest String Problem (CSP) is an NP-hard problem, which arises in computational molecular biology and coding theory. This class of problems is to find a string that minimizes the maximum Hamming distance to a gi...
详细信息
The Closest String Problem (CSP) is an NP-hard problem, which arises in computational molecular biology and coding theory. This class of problems is to find a string that minimizes the maximum Hamming distance to a given set of strings. In this paper, we present an exact algorithm called Distance First algorithm (DFA) for three strings of CSP with alphabet size two. For the general CSP, we design a polynomial heuristic which is a combination of our proposed approximation algorithm LDDA ([10] Liu Xiaolan, Fu Keqiang, Shao Renxiang. Largest distance decreasing algorithm for the Closest String Problem. journal of Information & Computational Science 2004;1(2): 287-92) and local search strategies. Numerical results show that the proposed heuristic may obtain a nearly optimal value in a reasonable time for small and large-scale instances of the CSP. (C) 2011 Elsevier Ltd. All rights reserved.
For graphs G and H, a homomorphism from G to H is a function phi: V(G) -> V(H), which maps vertices adjacent in G to adjacent vertices of H. A homomorphism is locally injective if no two vertices with a common neig...
详细信息
For graphs G and H, a homomorphism from G to H is a function phi: V(G) -> V(H), which maps vertices adjacent in G to adjacent vertices of H. A homomorphism is locally injective if no two vertices with a common neighbor are mapped to a single vertex in H. Many cases of graph homomorphism and locally injective graph homomorphism are NP-complete, so there is little hope to design polynomial-time algorithms for them. In this paper we present an algorithm for graph homomorphism and locally injective homomorphism working in time O*((b + 2)(vertical bar V(G)vertical bar)), where b is the bandwidth of the complement of H. (C) 2014 Elsevier B.V. All rights reserved.
We consider a problem of 2-partitioning a finite sequence of points in Euclidean space into two clusters of the given sizes with some additional constraints. The solution criterion is the minimum of the sum (over both...
详细信息
ISBN:
(数字)9783030386290
ISBN:
(纸本)9783030386290;9783030386283
We consider a problem of 2-partitioning a finite sequence of points in Euclidean space into two clusters of the given sizes with some additional constraints. The solution criterion is the minimum of the sum (over both clusters) of weighted intracluster sums of squared distances between the elements of each cluster and its center. The weights of the intracluster sums are equal to the cardinalities of the desired clusters. The center of one cluster is given as input, while the center of the other one is unknown and is determined as a geometric center, i.e. as a point of space equal to the mean of the cluster elements. The following constraints hold: the difference between the indices of two subsequent points included in the first cluster is bounded from above and below by given some constants. It is shown that the considered problem is the strongly NP-hard one. An exact algorithm is proposed for the case of integer-valued input of the problem. This algorithm has a pseudopolynomial running time if the space dimension is fixed.
This paper models a single liner service design and operations problem. The model selects the ports to be included, their sequence, the sailing speed of vessels, the number of vessels and the amounts of cargo to trans...
详细信息
This paper models a single liner service design and operations problem. The model selects the ports to be included, their sequence, the sailing speed of vessels, the number of vessels and the amounts of cargo to transport by the service. The objective is to maximise profit. First, a relaxation with a mixed-integer nonlinear programming (MINLP) formulation is proposed. We show how to obtain the optimal speed value. Once this value is obtained, the mathematical programming formulation becomes a mixed-integer linear program (MILP). Then, a two-step exact algorithm is presented to solve the problem. Using real data, the optimal solution was found in less than 1 min for small-size problems and in few hours for relatively large-size problems. More tests were carried out on randomly generated data sets with up to 25 ports. The results of these tests are rather promising, and they enabled us to identify the performance limits of the algorithm.
The purpose of this study is to propose an exact algorithm for the unrestricted block relocation problem with distinct priorities. In this problem, a storage area is considered where blocks of the same size are stacke...
详细信息
The purpose of this study is to propose an exact algorithm for the unrestricted block relocation problem with distinct priorities. In this problem, a storage area is considered where blocks of the same size are stacked vertically in tiers. Because we can access only topmost blocks, relocations of blocks are required when other blocks are retrieved. The objective is to minimize the total number of such relocations necessary for retrieving all the blocks one by one according to a specified order. In the restricted version of this problem, only the topmost block above the target block is relocatable. On the other hand, no such restriction is imposed on the unrestricted problem, which is considered in this study. We also assume that each block is assigned a distinct retrieval priority and the retrieval order of blocks is unique. To improve the efficiency of a branch-and-bound algorithm for this problem, we propose several dominance properties to eliminate unnecessary nodes in the search tree. Furthermore, we propose a new lower bound of the total number of relocations. The effectiveness of the proposed exact algorithm is verified by numerical experiments for benchmark instances in the literature. (C) 2018 Elsevier Ltd. All rights reserved.
In this paper, we study a minimum connected dominating set problem (CDS) in wireless networks, which selects a minimum CDS with property that all intermediate nodes inside every pairwise shortest path should be includ...
详细信息
In this paper, we study a minimum connected dominating set problem (CDS) in wireless networks, which selects a minimum CDS with property that all intermediate nodes inside every pairwise shortest path should be included. Such a minimum CDS (we name this problem as SPCDS) is an important tache of some other algorithms for constructing a minimum CDS. We prove that finding such a minimum SPCDS can be achieved in polynomial time and design an exact algorithm with time complexity O(delta (2) n), where delta is the maximum node degree in communication graph.
The maximum independent set problem is a basic NP-hard problem and has been extensively studied in exact algorithms. The maximum independent set problems in low-degree graphs are also important and may be bottlenecks ...
详细信息
The maximum independent set problem is a basic NP-hard problem and has been extensively studied in exact algorithms. The maximum independent set problems in low-degree graphs are also important and may be bottlenecks of the problem in general graphs. In this paper, we present a 1.1736(n)n(0(1))-time exact algorithm for the maximum independent set problem in an n-vertex graph with degree bounded by 5, improving the previous running time bound of 1.1895(n)n(0(1)). In our algorithm, we show that the graph after applying reduction rules always has a good local structure branching on which will effectively reduce the instance. Based on this, we obtain an improved algorithm without introducing a large number of branching rules. (C) 2014 Elsevier B.V. All rights reserved.
In this paper, we present an exact algorithm to find all extreme supported nondominated points of multiobjective mixed integer programs. The algorithm uses a composite linear objective function and finds all the desir...
详细信息
In this paper, we present an exact algorithm to find all extreme supported nondominated points of multiobjective mixed integer programs. The algorithm uses a composite linear objective function and finds all the desired points in a finite number of steps by changing the weights of the objective functions in a systematic way. We develop further variations of the algorithm to improve its computational performance and demonstrate our algorithm's performance on multiobjective assignment, knapsack, and traveling salesperson problems with three and four objectives.
We investigate sparse matrix bipartitioning - a problem where we minimize the communication volume in parallel sparse matrix-vector multiplication. We prove, by reduction from graph bisection, that this problem is N P...
详细信息
We investigate sparse matrix bipartitioning - a problem where we minimize the communication volume in parallel sparse matrix-vector multiplication. We prove, by reduction from graph bisection, that this problem is N P-complete in the case where each side of the bipartitioning must contain a linear fraction of the nonzeros. We present an improved exact branch-and-bound algorithm which finds the minimum communication volume for a given matrix and maximum allowed imbalance. The algorithm is based on a maximum-flow bound and a packing bound, which extend previous matching and packing bounds. We implemented the algorithm in a new program called MP (Matrix Partitioner), which solved 839 matrices from the SuiteSparse collection to optimality, each within 24 h of CPU-time. Furthermore, MP solved the difficult problem of the matrix cage6 in about 3 days. The new program is on average more than ten times faster than the previous program MondriaanOpt. Benchmark results using the set of 839 optimally solved matrices show that combining the mediumgrain/iterative refinement methods of the Mondriaan package with the hypergraph bipartitioner of the PaToH package produces sparse matrix bipartitionings on average within 10% of the optimal solution. (C) 2020 Elsevier B.V. All rights reserved.
暂无评论