检索结果-内蒙古大学图书馆

Efficient and exact reliability evaluation for networks with imperfect vertices

IEEE TRANSACTIONS ON RELIABILITY 2007年第2期56卷 288-300页

作者： Kuo, Sy-Yen Yeh, Fu-Min Lin, Hung-Yau Natl Taiwan Univ Dept Elect Engn Taipei 106 Taiwan Natl Taiwan Univ Sci & Technol Dept Comp Sci & Informat Engn Taipei Taiwan Gemtek Technol Co Ltd Hsinchu Taiwan Advantech Co Ltd Taipei Taiwan

The factoring theorem, and BDD-based algorithms have been shown to be efficient reliability evaluation methods for networks with perfectly reliable vertices. However, the vertices, and the links of a network may fail in the real world. Imperfect vertices can be factored like links, but the complexity increases exponentially with their number. exact algorithms based on the factoring theorem can therefore induce great overhead if vertex failures are taken into account. To solve the problem, a set of exact algorithms is presented to deal with vertex failures with little additional overhead. The algorithms can be used to solve terminal-pair, k-terminal, and all-terminal reliability problems in directed, and undirected networks. The essential variable is defined to be a vertex or a link of a network whose failure has the dominating effect on network reliability. The algorithms are so efficient that it takes less than 1.2 seconds on a 1.67 GHz personal computer to identify the essential variable of a network having 2'9 paths. When vertex failures in a 3 x 10 mesh network are taken into account, the proposed algorithms can induce as little as about 0.3% of runtime overhead, while the best result from factoring algorithms incurs about 300% overhead.

关键词： BDD (Binary Decision Diagrams) Boolean formula exact algorithm network reliability

来源：评论

学校读者我要写书评

暂无评论

Global and local optimisation-based hybrid approach for cloud service composition

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL SCIENCE AND ENGINEERING 2018年第1期17卷 1-14页

作者： Shetty, Jyothi D'Mello, Demian Antony Srinivas Sch Engn Dept Comp Sci & Engn Mukka India Canara Engn Coll Dept Comp Sci & Engn Mangalore India

The goal of service composition is to find the best set of services, which meets the user requirements. The efficient local optimisation methods may fail to satisfy user's end-to-end requirements. Global optimisation methods are popular when the user's end-to-end requirements are to be satisfied. Optimal composition to end-to-end requirements consumes exponential time, in case of large search space. Metaheuristic methods are being used to solve this problem, which gives near optimal solution. The authors propose an approach in which both local and global optimisation are used. In order to avoid local optimums during local optimisation, the proposed work selects a set of best services from each task and then uses a global optimisation method on the smaller search space to select the best composition. In order to reduce the communication costs, optimal solution identifies the minimum number of clouds for composition.

关键词： cloud service service composition task level selection global optimisation local optimisation exact algorithm

来源：评论

学校读者我要写书评

暂无评论

The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study

引用

MATHEMATICAL PROGRAMMING COMPUTATION 2018年第4期10卷 487-532页

作者： Juhl, Daniel Warme, David M. Winter, Pawel Zachariasen, Martin Univ Copenhagen Dept Comp Sci DK-2100 Copenhagen O Denmark Grp W Inc 2650 Pk Tower DrSuite 500 Vienna VA 22180 USA

The GeoSteiner software package has for about 20 years been the fastest (publicly available) program for computing exact solutions to Steiner tree problems in the plane. The computational study by Warme, Winter and Zachariasen, published in 2000, documented the performance of the GeoSteiner approach-allowing the exact solution of Steiner tree problems with more than a thousand terminals. Since then, a number of algorithmic enhancements have improved the performance of the software package significantly. We describe these (previously unpublished) enhancements, and present a new computational study wherein we run the current code on the largest problem instances from the 2000-study, and on a number of larger problem instances. The computational study is performed using the commercial GeoSteiner 4.0 code base, and the performance is compared to the publicly available GeoSteiner 3.1 code base as well as the code base from the 2000-study. The software studied in the paper is being released as GeoSteiner 5.0 under an open source license.

关键词： Euclidean Steiner tree problem Rectilinear Steiner tree problem Fixed orientation Steiner tree problem exact algorithm Computational study

来源：评论

学校读者我要写书评

暂无评论

ESKEMAP: exact sketch-based read mapping

引用

algorithmS FOR MOLECULAR BIOLOGY 2024年第1期19卷 19页

作者： Schulz, Tizian Medvedev, Paul Bielefeld Univ Fac Technol Bielefeld Germany Bielefeld Univ Ctr Biotechnol CeBiTec Bielefeld Germany Bielefeld Univ Bielefeld Inst Bioinformat Infrastruct BIBI Bielefeld Germany Bielefeld Univ Grad Sch Digital Infrastruct Life Sci DILS Bielefeld Germany Penn State Univ Dept Comp Sci & Engn University Pk PA 16802 USA Penn State Univ Dept Biochem & Mol Biol University Pk PA 16802 USA Penn State Univ Huck Inst Life Sci University Pk PA 16802 USA

Background Given a sequencing read, the broad goal of read mapping is to find the location(s) in the reference genome that have a "similar sequence". Traditionally, "similar sequence" was defined as having a high alignment score and read mappers were viewed as heuristic solutions to this well-defined problem. For sketch-based mappers, however, there has not been a problem formulation to capture what problem an exact sketch-based mapping algorithm should solve. Moreover, there is no sketch-based method that can find all possible mapping positions for a read above a certain score *** In this paper, we formulate the problem of read mapping at the level of sequence sketches. We give an exact dynamic programming algorithm that finds all hits above a given similarity threshold. It runs in O ( | t | + | p | + & ell;2 ) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O} (|t| + |p| + \ell <^>2)$$\end{document} time and O ( & ell;log & ell;) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O} (\ell \log \ell )$$\end{document} space, where |t| is the number of k \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document} -mers inside the sketch of the reference, |p| is the number of k \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{doc

关键词： Sequence sketching Long-read mapping exact algorithm Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Computing Euclidean Steiner trees over segments

引用

EURO JOURNAL ON COMPUTATIONAL OPTIMIZATION 2020年第3-4期8卷 309-325页

作者： Althaus, Ernst Rauterberg, Felix Ziegler, Sarah Johannes Gutenberg Univ Mainz Mainz Germany Tech Univ Darmstadt Darmstadt Germany

In the classical Euclidean Steiner minimum tree (SMT) problem, we are given a set of points in the Euclidean plane and we are supposed to find the minimum length tree that connects all these points, allowing the addition of arbitrary additional points. We investigate the variant of the problem where the input is a set of line segments. We allow these segments to have length 0, i.e., they are points and hence we generalize the classical problem. Furthermore, they are allowed to intersect such that we can model polygonal input. As in the GeoSteiner approach of Juhl et al. (Math Program Comput 10(2):487-532, 2018) for the classical case, we use a two-phase approach where we construct a superset of so-called full components of an SMT in the first phase. We prove a structural theorem for these full components, which allows us to use almost the same GeoSteiner algorithm as in the classical SMT problem. The second phase, the selection of a minimal cost subset of constructed full components, is exactly the same as in GeoSteiner approach. Finally, we report some experimental results that show that our approach is more efficient than the approximate solution that is obtained by sampling the segments.

关键词： Euclidean Steiner minimum tree exact algorithm Structural theorem

来源：评论

学校读者我要写书评

暂无评论

Constructing two-level QB-optimal screening designs using mixed-integer programming and heuristic algorithms

引用

STATISTICS AND COMPUTING 2023年第1期33卷 1-18页

作者： Vazquez, Alan R. Wong, Weng Kee Goos, Peter Univ Arkansas Dept Ind Engn Fayetteville AR 72701 USA Univ Calif Los Angeles Dept Biostat Los Angeles CA USA Katholieke Univ Leuven Dept Biosyst Leuven Belgium Univ Antwerp Dept Engn Management Antwerp Belgium

Two-level screening designs are widely applied in manufacturing industry to identify influential factors of a system. These designs have each factor at two levels and are traditionally constructed using standard algorithms, which rely on a pre-specified linear model. Since the assumed model may depart from the truth, two-level Q(B)-optimal designs have been developed to provide efficient parameter estimates for several potential models. These designs also have an overarching goal that models that are more likely to be the best for explaining the data are estimated more efficiently than the rest. However, there is no effective algorithm for constructing them. This article proposes two methods: a mixed-integer programming algorithm that guarantees convergence to the two-level Q(B)-optimal designs;and, a heuristic algorithm that employs a novel formula to find good designs in short computing times. Using numerical experiments, we show that our mixed-integer programming algorithm is attractive to find small optimal designs, and our heuristic algorithm is the most computationally-effective approach to construct both small and large designs, when compared to benchmark heuristic algorithms.

关键词： Coordinate exchange exact algorithm Iterated local search Model robust Orthogonal design PBCE algorithm

来源：评论

学校读者我要写书评

暂无评论

Particle filters for partially observed diffusions

引用

JOURNAL OF THE ROYAL STATISTICAL SOCIETY SERIES B-STATISTICAL METHODOLOGY 2008年第4期70卷 755-777页

作者： Fearnhead, Paul Papaspiliopoulos, Omiros Roberts, Gareth O. Univ Lancaster Lancaster LA1 4YW England Univ Warwick Coventry CV4 7AL W Midlands England

We introduce a novel particle filter scheme for a class of partially observed multivariate diffusions. We consider a variety of observation schemes, including diffusion observed with error, observation of a subset of the components of the multivariate diffusion and arrival times of a Poisson process whose intensity is a known function of the diffusion (Cox process). Unlike currently available methods, our particle filters do not require approximations of the transition and/or the observation density by using time discretizations. Instead, they build on recent methodology for the exact simulation of the diffusion process and the unbiased estimation of the transition density. We introduce the generalized Poisson estimator, which generalizes the Poisson estimator of Beskos and co-workers. A central limit theorem is given for our particle filter scheme.

关键词： auxiliary variables central limit theorem continuous time particle filtering Cox process exact algorithm

来源：评论

学校读者我要写书评

暂无评论

Critical edges for the assignment problem: Complexity and exact resolution

引用

OPERATIONS RESEARCH LETTERS 2013年第6期41卷 685-689页

作者： Bazgan, Cristina Toubaline, Sonia Vanderpooten, Daniel Univ Paris 09 PSL LAMSADE UMR 7243 F-75775 Paris 16 France Inst Univ France Paris France UCL Dept Secur & Crime Sci London WC1E 6BT England

This paper investigates two problems related to the determination of critical edges for the minimum cost assignment problem. Given a complete bipartite balanced graph with n vertices on each part and with costs on its edges, k MOST VITAL EDGES ASSIGNMENT consists of determining a set of k edges whose removal results in the largest increase in the cost of a minimum cost assignment. A dual problem, MIN EDGE BLOCKER ASSIGNMENT, consists of removing a subset of edges of minimum cardinality such that the cost of a minimum cost assignment in the remaining graph is larger than or equal to a specified threshold. We show that k MOST VITAL EDGES ASSIGNMENT is NP-hard to approximate within a factor c < 2 and MIN EDGE BLOCKER ASSIGNMENT is NP-hard to approximate within a factor 1.36. We also provide an exact algorithm for k MOST VITAL EDGES ASSIGNMENT that runs in O(n(k+2)). This algorithm can also be used to solve exactly MIN EDGE BLOCKER ASSIGNMENT. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Most vital edges Min edge blocker Assignment problem Complexity Approximation exact algorithm

来源：评论

学校读者我要写书评

暂无评论

exact and Metaheuristic algorithms for Variable Reduction

引用

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION 2024年第6期28卷 1704-1718页

作者： Song, Aijuan Wu, Guohua Zhou, Ling Wang, Ling Pedrycz, Witold Cent South Univ Sch Traff & Transportat Engn Changsha 410075 Peoples R China Tsinghua Univ Dept Automat Beijing 100084 Peoples R China Univ Alberta Dept Elect & Comp Engn Edmonton AB T6G 2V4 Canada Polish Acad Sci Syst Res Inst PL-01447 Warsaw Poland

A variable reduction strategy (VRS) drives evolutionary algorithms (EAs) to evolve more effectively by simplifying optimization problems. To represent a decision space with the smallest set of variables via VRS, a variable reduction optimization problem (VROP) has been defined, which could be handled by a heuristic rule-based automatic variable reduction algorithm (HR-AVRA). However, HR-AVRA has limitations in identifying an optimal solution and is susceptible of getting trapped in local optimums. To handle these challenges, we propose to solve VROP with exact and metaheuristic algorithms. We construct a linear programming model of VROP for the first time. Then, Gurobi, an exact algorithm optimizer, is employed to seek and identify an optimal solution for it. Subsequently, we design two representative single-point-based and population-based metaheuristic algorithms, simulated annealing-based (SA-AVRA) and ant colony optimization-based (ACO-AVRA) methods, to solve VROP more effectively. These variable reduction algorithms can group variables of a continuous optimization problem into reduced and core variables, with the latter representing both reduced variables and the entire decision space. Extensive experiments verify that Gurobi can provide optimal solutions for small-scale VROPs, while SA/ACO-AVRA enables more reduced variables than other variable reduction methods. We also integrate various variable reduction algorithms with several competitive EAs to tackle equality-constrained optimization problems and nonlinear equations systems. Experiments show that EAs integrated with a variable reduction algorithm outperform both standard EAs and those with several other complexity reduction methods. Furthermore, integrating a variable reduction algorithm that introduces more reduced variables generally can lead to better performance of EAs.

关键词： Mathematical models Search problems Metaheuristics Standards Simulated annealing Linear programming Diversity reception Continuous optimization problem evolutionary algorithm (EA) exact algorithm metaheuristic algorithm variable reduction optimization problem (VROP)

来源：评论

学校读者我要写书评

暂无评论

Optimization of machine schedules and vehicle routes in the mobile additive manufacturing mode

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2024年

作者： Yuan, Biao Cui, Weiwei Shanghai Jiao Tong Univ Sino US Global Logist Inst Data Driven Management Decis Making Lab Shanghai Peoples R China Shanghai Univ Sch Management Shanghai Peoples R China Shanghai Key Lab Intelligent Mfg & Robot Shanghai Peoples R China

Online shopping giant Amazon proposes to use 3D printers mounted on vehicles to print customer purchases on the fly and deliver them immediately. Because of the overlap between production and transportation processes, such a mobile manufacturing mode offers potential savings in lead times and inventory costs. However, the decisions associated with the two processes are intertwined, making it challenging to achieve satisfactory machine schedules and vehicle routes. To address the situation and fully understand the benefits of the mode, we study a related optimisation problem of finding routes for vehicles and production schedules for 3D printers mounted on them with minimum travel costs. First, we construct a mixed-integer programming model to formulate the problem. Then, we develop an exact algorithm to solve it. Specifically, we propose two propositions about the optimal production schedule of machines in the route and develop a labelling algorithm for the pricing problem. And we devise a problem-specific heuristic labelling algorithm to speed up column generation. We use two sizes of instances with five problem parameter settings (including 290 instances) to validate the effectiveness of the algorithm. In addition, we provide some managerial insights for decision-makers by comparing the novel mode with the traditional manufacturing mode.

关键词： Additive manufacturing mobile manufacturing machine scheduling routing exact algorithm SDG 9: Industry, innovation and infrastructure

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：