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

An efficient probability-based VNS algorithm for delivery territory design

COMPUTERS & OPERATIONS RESEARCH 2024年 170卷

作者： Aly, Ahmed Gabor, Adriana F. Mladenovic, Nenad Sleptchenko, Andrei Khalifa Univ Dept Math Abu Dhabi U Arab Emirates Khalifa Univ Dept Management Sci & Engn Abu Dhabi U Arab Emirates Khalifa Univ Res Ctr Digital Supply Chain & Operat Management Abu Dhabi U Arab Emirates

This paper deals with the Delivery Territory Design Problem (DTDP), a districting problem that often occurs in delivery operations. The goal of the problem is to construct clusters of nodes (territories) such that the maximum diameter of a territory is minimized, while the territories designed are balanced w.r.t. some performance measures. We propose to solve the DTDP using a Probabilistic Variable Neighborhood Search (ProbVNS) algorithm based on two local search procedures: a tailored randomized shake procedure that targets both a reduction of infeasibility and diversification, and a deterministic local search based on a linear combination of objective and constraint violation. In addition to searching in different neighborhoods, the ProbVNS also changes the search direction by exploring different penalties for violating constraints. Numerical experiments show that ProbVNS outperforms a recent GRASP with the Path-Relinking (PR) algorithm proposed in the literature in terms of feasibility and objective value. In the tested instances, ProbVNS obtained a lower infeasibility measure in 90% of the instances. For these instances, the average decrease in the objective value was 8.3%, with a maximum decrease of 51%. Finally, the running times of ProbVNS are, on average, 2.7 times lower than those of PR.

关键词： Territory design Clustering Variable neighborhood search (VNS) randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

DAGWOOD - A SYSTEM FOR MANIPULATING POLYNOMIALS GIVEN BY STRAIGHT-LINE PROGRAMS

引用

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 1988年第3期14卷 218-240页

作者： FREEMAN, TS IMIRZIAN, GM KALTOFEN, E YAGATI, L CARNEGIE MELLON UNIV DEPT COMP SCIPITTSBURGHPA 15213 MATH SCI RES INST BERKELEYCA 94720 RENSSELAER POLYTECH INST TROYNY 12181

We discuss the design, implementation, benchmarking of a system that can manipulate symbolic expressions represented by their straight-line computations. Our system is capable of performing rational arithmetic on, evaluating, differentiating, taking greatest common divisors of, factoring polynomials in straight-line format. The straight-line results can also be converted to stard sparse format. We show by example that our system can hle prob- lems for which conventional methods lead to excessive intermediate expression swell.

关键词： factorization implementation in LISP implicit representation multivariate polynomial program optimization randomized algorithm straight-line program

来源：评论

学校读者我要写书评

暂无评论

MULTIWAY MONTE CARLO METHOD FOR LINEAR SYSTEMS

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2019年第6期41卷 A3449-A3475页

作者： Wu, Tao Gleich, David F. Purdue Univ Dept Comp Sci W Lafayette IN 47906 USA

We study a novel variation on the Ulam-von Neumann Monte Carlo method for solving a linear system. This is an old randomized procedure that results from using a random walk to stochastically evaluate terms in the Neumann series. In order to apply this procedure, the variance of the stochastic estimator needs to be bounded. The best known sufficient condition for bounding the variance is that the infinity norm of the matrix in the Neumann series is smaller than one, which greatly limits the usability of this method. We improve this condition by proposing a new stochastic estimator based on a different type of random walk. Our multiway walk and estimator is based on a time-inhomogeneous Markov process that iterates through a sequence of transition matrices built from the original linear system. For our new method, we prove that a necessary and sufficient condition for convergence is that the spectral radius of the elementwise absolute value of the matrix underlying the Neumann series is smaller than one. This is a strictly weaker condition than currently exists. In addition, our new method is often faster than the standard algorithm. Through experiments, we demonstrate the potential for our method to reduce the time needed to solve linear equations by incorporating it into an outer iterative method.

关键词： Markov chain Monte Carlo linear solver randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

XTRACE: MAKING THE MOST OF EVERY SAMPLE IN STOCHASTIC TRACE ESTIMATION

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2024年第1期45卷 1-23页

作者： Epperly, Ethan N. Tropp, Joel A. Webber, Robert J. CALTECH Div Comp & Math Sci Pasadena CA 91125 USA

The implicit trace estimation problem asks for an approximation of the trace of a square matrix, accessed via matrix-vector products (matvecs). This paper designs new randomized algorithms, XTRACE and XNYsTRACE, for the trace estimation problem by exploiting both variance reduction and the exchangeability principle. For a fixed budget of matvecs, numerical experiments show that the new methods can achieve errors that are orders of magnitude smaller than existing algorithms, such as the Girard-Hutchinson estimator or the Hutch++ estimator. A theoretical analysis confirms the benefits by offering a precise description of the performance of these algorithms as a function of the spectrum of the input matrix. The paper also develops an exchangeable estimator, XDiag, for approximating the diagonal of a square matrix using matvecs.

关键词： trace estimation low-rank approximation exchangeability variance reduction randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Tikhonov regularization with MTRSVD method for solving large-scale discrete ill-posed problems

引用

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 2022年第0期405卷 113969-113969页

作者： Huang, Guangxin Liu, Yuanyuan Yin, Feng Chengdu Univ Technol Coll Math & Phys Geomath Key Lab Sichuan Chengdu 610059 Peoples R China Sichuan Univ Sci & Engn Coll Math & Stat Zigong 643000 Peoples R China

Regularization is possibly the most popular method for solving discrete ill-posed prob-lems, whose solution is less sensitive to the error in the observed vector in the right hand than the original solution. This paper presents a new modified truncated randomized singular value decomposition (TR-MTRSVD) method for large Tikhonov regularization in standard form. The proposed TR-MTRSVD algorithm introduces the idea of randomized algorithm into the improved truncated singular value decomposition (MTSVD) method to solve large Tikhonov regularization problems. The approximation matrix A & SIM;l produced by randomized SVD is replaced by the closest matrix A & SIM;k & SIM;in a unitarily invariant matrix norm with the same spectral condition number. The regularization parameters are determined by the discrepancy principle. Numerical examples show the effectiveness and efficiency of the proposed TR-MTRSVD algorithm for large Tikhonov regularization problems. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Linear discrete ill-posed problem Tikhonov regularization MTSVD randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Jacobian sparsity detection using Bloom filters

引用

OPTIMIZATION METHODS & SOFTWARE 2024年

作者： Hovland, Paul D. Argonne Natl Lab Res Partnerships 9700 S Cass Ave Lemont IL 60439 USA

Determining Jacobian sparsity structure is an important step in the efficient computation of sparse Jacobians. We introduce a new method for determining Jacobian sparsity patterns by combining bit vector probing with Bloom filters. We further refine Bloom filter probing by combining it with hierarchical probing to yield a highly effective strategy for Jacobian sparsity pattern determination.

关键词： Sparsity automatic differentiation Bloom filter randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Discovering affine equalities using random interpretation

引用

ACM SIGPLAN NOTICES 2003年第1期38卷 74-84页

作者： Gulwani, S Necula, GC Univ Calif Berkeley Berkeley CA 94720 USA

We present a new polynomial-time randomized algorithm for discovering affine equalities involving variables in a program. The key idea of the algorithm is to execute a code fragment on a few random inputs, but in such a way that all paths are covered on each run. This makes it possible to rule out invalid relationships even with very few runs. The algorithm is based on two main techniques. First, both branches of a conditional are executed on each run and at joint points we perform an affine combination of the joining states. Secondly, in the branches of an equality conditional we adjust the data values on the fly to reflect the truth value of the guarding boolean expression. This increases the number of affine equalities that the analysis discovers. The algorithm is simpler to implement than alternative deterministic versions, has better computational complexity, and has an extremely small probability of error for even a small number of runs. This algorithm is an example of how randomization can provide a trade-off between the cost and complexity of program analysis, and a small probability of unsoundness.

关键词： algorithms theory verification affine relationships linear equalities random interpretation randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Adaptive surrogate model coupled with stochastic configuration network strategies for time-dependent reliability assessment

引用

PROBABILISTIC ENGINEERING MECHANICS 2023年 71卷

作者： Liu, Huizhen Li, Shangjie Huang, Xianzhen Northeastern Univ Sch Mech Engn & Automation Shenyang 110819 Peoples R China Northeastern Univ Key Lab Vibrat & Control Aeroprop Syst Minist Educ China Shenyang 110819 Peoples R China

Time-dependent reliability assessment is crucial in enhancing product development economics and product performance sustainability throughout the lifecycle. It is still a challenge to accurately and efficiently evaluate the time-dependent reliability of engineering systems. This paper proposes a novel adaptive surrogate model method combining stochastic configuration network (SCN) and Kriging strategies to evaluate time-dependent reliability. SCN has accurate approximation ability and learning efficiency for strongly nonlinear systems that can overcome the conventional time-dependent reliability calculation, which is time-consuming and characterized by low accuracy. The proposed method first applies SCN to establish the response model of the performance function with respect to time and obtain the extreme value of the performance function. Then, Kriging is used to establish the extreme value model of the performance function with respect to the random variables based on the extreme value of performance function. The adaptive process considering the characteristics of random variables samples is adopted to update the extreme value model until the model meets the confidence target. Lastly, Monte Carlo simulation is employed for time-dependent reliability assessment based on the established extreme value model. Three example studies are used to demonstrate the effectiveness of the proposed approach for time-dependent reliability assessment.

关键词： Surrogate model randomized algorithm Stochastic configuration network Adaptive Kriging Time-dependent reliability

来源：评论

学校读者我要写书评

暂无评论

On the difference set of two transductions

引用

THEORETICAL COMPUTER SCIENCE 2024年 1016卷

作者： Konstantinidis, Stavros Moreira, Nelma Reis, Rogerio Sebej, Juraj St Marys Univ Math & CS 923 Robie Str Halifax NS B3H 3C3 Canada Univ Porto Fac Ciencias CMUP & DM DCC Rua Campo Alegre P-4169007 Porto Portugal Safarik Univ Inst Comp Sci Fac Sci Kosice Slovakia

The difference set ds,t of two (nondeterministic, in general) transducers s, t is the set of all input words for which the output sets of the two transducers are not equal. When the two transducers realize homomorphisms, their difference set is the complement of the well known equality set of the two homomorphisms. However, we show that transducer difference sets result in Chomskylike classes of languages that are different than the classes resulting from equality sets. We also consider the following word problem: given transducers s, t and input w, tell whether the output sets s(w) and t(w) are different. In general the problem is PSPACE-complete, but it becomes NP-complete when at least one of the given transducers has finite outputs. We also provide a PRAX (polynomial randomized approximation) algorithm for the word problem as well as for the NFA (in)equivalence problem. Our presentation of PRAX algorithms improves the original presentation.

关键词： Transducer Difference set Equality set Counter machine Approximation algorithm randomized algorithm NFA equivalence

来源：评论

学校读者我要写书评

暂无评论

Signature-Free Asynchronous Binary Byzantine Consensus with t < n/3, O(n²) Messages, and O(1) Expected Time

引用

JOURNAL OF THE ACM 2015年第4期62卷 31-31页

作者： Mostefaoui, Achour Moumen, Hamouma Raynal, Michel Univ Nantes LINA F-44322 Nantes France Univ Bejaia LMA Bejaia 06000 Algeria Inst Univ France F-35042 Rennes France Univ Rennes IRISA F-35042 Rennes France

This article is on broadcast and agreement in asynchronous message-passing systems made up of n processes, and where up to t processes may have a Byzantine Behavior. Its first contribution is a powerful, yet simple, all-to-all broadcast communication abstraction suited to binary values. This abstraction, which copes with up to t < n/3 Byzantine processes, allows each process to broadcast a binary value, and obtain a set of values such that ( 1) no value broadcast only by Byzantine processes can belong to the set of a correct process, and ( 2) if the set obtained by a correct process contains a single value v, then the set obtained by any correct process contains v. The second contribution of this article is a new round-based asynchronous consensus algorithm that copes with up to t < n/3 Byzantine processes. This algorithm is based on the previous binary broadcast abstraction and a weak common coin. In addition to being signature-free and optimal with respect to the value of t, this consensus algorithm has several noteworthy properties: the expected number of rounds to decide is constant;each round is composed of a constant number of communication steps and involves O(n(2)) messages;each message is composed of a round number plus a constant number of bits. Moreover, the algorithm tolerates message reordering by the adversary (i.e., the Byzantine processes).

关键词： algorithms Reliability Theory Asynchronous message-passing system broadcast abstraction Byzantine process common coin consensus distributed algorithm optimal resilience randomized algorithm signature-free algorithm simplicity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：