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

A metaheuristic framework for stochastic combinatorial optimization problems based on GPGPU with a case study on the probabilistic traveling salesman problem with deadlines

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2013年第1期73卷 74-85页

作者： Weyland, Dennis Montemanni, Roberto Gambardella, Luca Maria IDSIA Ist Dalle Molle Studi Intelligenza Artificiale CH-6928 Manno Lugano Switzerland

In this work we propose a general metaheuristic framework for solving stochastic combinatorial optimization problems based on general-purpose computing on graphics processing units (GPGPU). This framework is applied to the probabilistic traveling salesman problem with deadlines (PTSPD) as a case study. Computational studies reveal significant improvements over state-of-the-art methods for the PTSPD. Additionally, our results reveal the huge potential of the proposed framework and sampling-based methods for stochastic combinatorial optimization problems. (C) 2012 Elsevier Inc. All rights reserved.

关键词： GPGPU CUDA stochastic combinatorial optimization stochastic vehicle routing Monte Carlo sampling

来源：评论

学校读者我要写书评

暂无评论

SimILS: a simulation-based extension of the iterated local search metaheuristic for stochastic combinatorial optimization

引用

JOURNAL OF SIMULATION 2016年第1期10卷 69-77页

作者： Grasas, Alex Juan, Angel A. Lourenco, Helena R. EADA Business Sch Barcelona 08011 Spain Open Univ Catalonia IN3 Barcelona Spain Univ Pompeu Fabra Barcelona Spain

Iterated Local Search (ILS) is one of the most popular single-solution-based metaheuristics. ILS is recognized by many authors as a relatively simple yet efficient framework able to deal with complex combinatorial optimization problems (COPs). ILS-based algorithms have been successfully applied to provide near-optimal solutions to different COPs in logistics, transportation, production, etc. However, ILS is designed to solve COPs under deterministic scenarios. In some real-life applications where uncertainty is present, the deterministic assumption makes the model less accurate since it does not reflect the real stochastic nature of the system. This paper presents the SimILS framework that extends ILS by integrating simulation to be able to cope with stochastic COPs in a natural way. The paper also describes several tested applications that illustrate the main concepts behind SimILS and give rise to a new brand of ILS-based algorithms.

关键词： iterated local search simulation stochastic combinatorial optimization simheuristics

来源：评论

学校读者我要写书评

暂无评论

Global optima results for the Kauffman NK model

引用

MATHEMATICAL PROGRAMMING 2006年第2期106卷 319-338页

作者： Kaul, H Jacobson, SH Univ Illinois Dept Math Urbana IL 61801 USA Univ Illinois Dept Mech & Ind Engn Urbana IL 61801 USA

The Kauffman NK model has been used in theoretical biology, physics and business organizations to model complex systems with interacting components. Recent NK model results have focused on local optima. This paper analyzes global optima of the NK model. The resulting global optimization problem is transformed into a stochastic network model that is closely related to two well-studied problems in operations research. This leads to applicable strategies for explicit computation of bounds on the global optima particularly with K either small or close to N. A general lower bound, which is sharp for K = 0, is obtained for the expected value of the global optimum of the NK model. A detailed analysis is provided for the expectation and variance of the global optimum when K = N-1. The lower and upper bounds on the expectation obtained for this case show that there is a wide gap between the values of the local and the global optima. They also indicate that the complexity catastrophe that occurs with the local optima does not arise for the global optima.

关键词： NK model stochastic combinatorial optimization stochastic networks PERT order statistics

来源：评论

学校读者我要写书评

暂无评论

Tabu search when noise is present: An illustration in the context of cause and effect analysis

引用

JOURNAL OF HEURISTICS 1998年第1期4卷 5-23页

作者： Costa, D Silver, EA Univ Neuchatel Grp Stat CH-2002 Neuchatel Switzerland Univ Calgary Fac Management Calgary AB T2N 1N4 Canada

In the field of combinatorial optimization, it may be possible to more accurately represent reality through stochastic models rather than deterministic ones. When randomness is present in a problem, algorithm designers face new difficulties which complicate their task significantly. Finding a proper mathematical formulation and a fast evaluation of the objective function are two major issues. In this paper we propose a new tabu search algorithm based on sampling and statistical tests. The algorithm is shown to perform well in a stochastic environment where the quality of feasible solutions cannot be computed easily. This new search principle is illustrated in the field of cause and effect analysis where the true cause of an undesirable effect needs to be eliminated. A set of n potential causes is identified and each of them is assumed to be the true cause with a given probability. The time to investigate a cause is a random variable with a known probability distribution. Associated with each cause is the reward obtained if the cause is really the true cause. The decision problem is to sequence the n potential causes so as to maximize the expected reward realized before a specified time horizon.

关键词： cause and effect analysis sampling statistical tests stochastic combinatorial optimization tabu search

来源：评论

学校读者我要写书评

暂无评论

New global optima results for the Kauffman N K model:: handling dependency

引用

MATHEMATICAL PROGRAMMING 2006年第2-3期108卷 475-494页

作者： Kaul, Hemanshu Jacobson, Sheldon H. Univ Illinois Dept Math Urbana IL 61801 USA Univ Illinois Dept Mech & Ind Engn Urbana IL 61801 USA

The Kauffman NK model has been used in theoretical biology, physics and business organizations to model complex systems with interacting components. This paper presents new global optima results for the NK model by developing tools for handling dependency in the cases where K grows with N;this generalizes the previous work that focused on the analysis of the (independent) case K=N-1. A dependency graph is defined and studied to handle dependencies among underlying random variables in the NK model. Order statistics (with dependencies) and the expected value of the global optima, E-N,E- K, are bounded using equitable coloring of the dependency graph. These bounds convert the problem of bounding order statistics of dependent random variables into that of independent random variables while incorporating quantitative information about the mutual dependencies between the underlying random variables. An alternative upper bound on E-N,E- K using direct arguments is also proposed. A detailed analysis of E-N,E- K for K close to N (K=N-alpha and K=beta N, alpha is an element of Z(+),beta is an element of (0,1)) is given for underlying uniform and normal distributions. Finally, for bounded underlying distributions, the global optima is shown to be concentrated around its mean E-N,E- K.

关键词： NK model stochastic combinatorial optimization order statistics dependency graph equitable coloring of graphs concentration of measure

来源：评论

学校读者我要写书评

暂无评论

On the computational complexity of the Probabilistic Traveling Salesman Problem with Deadlines

引用

THEORETICAL COMPUTER SCIENCE 2014年第1期540卷 156-168页

作者： Weyland, D. USI SUPSI IDSIA Dalle Molle Inst Artificial Intelligence CH-6928 Manno Lugano Switzerland

The PROBABILISTIC TRAVELING SALESMAN PROBLEM WITH DEADLINES (PTSPD) is a stochastic vehicle routing problem considering time dependencies in terms of deadlines. The evaluation of the PTSPD objective function is believed to be a computationally demanding task and all efforts to find a polynomial time approach have failed so far. On the other hand, no hardness results regarding the evaluation of the PTSPD objective function are known. We fill this gap and show that the evaluation of the PTSPD objective function is indeed a computationally demanding task: even for Euclidean instances this task is #P-hard. We then derive additional hardness results for different computational tasks related to the PTSPD. Among other results, we show that the decision variant and the optimization variant of the PTSPD are both #P-hard. Following this, we focus on polynomial time approximations of the PTSPD objective function. We prove the existence of an FPRAS under certain conditions and examine the approximation guarantees obtained by the existing approaches. Finally, we give a strong inapproximability result regarding the objective function of a slightly more general problem, the DEPENDENT PTSPD. (C) 2013 Elsevier B.V. All rights reserved.

关键词： stochastic combinatorial optimization stochastic vehicle routing Computational complexity Inapproximability

来源：评论

学校读者我要写书评

暂无评论

Low-autocorrelation binary sequences: On improved merit factors and runtime predictions to achieve them

引用

APPLIED SOFT COMPUTING 2017年 56卷 262-285页

作者： Boskovic, Borko Brglez, Franc Brest, Janez Univ Maribor Fac Elect Engn & Comp Sci SI-2000 Maribor Slovenia NC State Univ Comp Sci Raleigh NC 27695 USA

The search for binary sequences with a high figure of merit, known as the low autocorrelation binary sequence (labs) problem, represents a formidable computational challenge. To mitigate the computational constraints of the problem, we consider solvers that accept odd values of sequence length L and return solutions for skew- symmetric binary sequences only - with the consequence that not all best solutions under this constraint will be optimal for each L. In order to improve both, the search for best merit factor and the asymptotic runtime performance, we instrumented three stochastic solvers, the first two are state-of-the-art solvers that rely on variants of memetic and tabu search (lssMAts and lssRRts), the third solver (lssOrel) organizes the search as a sequence of independent contiguous self-avoiding walk segments. By adapting a rigorous statistical methodology to performance testing of all three combinatorial solvers, experiments show that the solver with the best asymptotic average-case performance, lssOrel_8 = 0.000032 * 1.1504(I), has the best chance of finding solutions that improve, as L increases, figures of merit reported to date. The same methodology can be applied to engineering new labs solvers that may return merit factors even closer to the conjectured asymptotic value of 12.3248. (c) 2017 Elsevier B.V. All rights reserved.

关键词： Low-autocorrelation binary sequences Self-avoiding walk stochastic combinatorial optimization Asymptotic average-case performance

来源：评论

学校读者我要写书评

暂无评论

A Test Score-Based Approach to stochastic Submodular optimization

引用

MANAGEMENT SCIENCE 2021年第2期67卷 1075-1092页

作者： Sekar, Shreyas Vojnovic, Milan Yun, Se-Young Harvard Univ Harvard Business Sch Boston MA 02163 USA London Sch Econ LSE Dept Stat London WC2A 2AE England Korea Adv Inst Sci & Technol KAIST Grad Sch Artificial Intelligence Daejeon 34141 South Korea

We study the canonical problem of maximizing a stochastic submodular function subject to a cardinality constraint, where the goal is to select a subset from a ground set of items with uncertain individual performances to maximize their expected group value. Although near-optimal algorithms have been proposed for this problem, practical concerns regarding scalability, compatibility with distributed implementation, and expensive oracle queries persist in large-scale applications. Motivated by online platforms that rely on individual item scores for content recommendation and team selection, we study a special class of algorithms that select items based solely on individual performance measures known as test scores. The central contribution of this work is a novel and systematic framework for designing test score-based algorithms for a broad class of naturally occurring utility functions. We introduce a new scoring mechanism that we refer to as replication test scores and prove that as long as the objective function satisfies a diminishing-returns condition, one can leverage these scores to compute solutions that are within a constant factor of the optimum. We then extend these scoring mechanisms to the more general stochastic submodular welfare-maximization problem, where the goal is to partition items into groups to maximize the sum of the expected group values. For this more difficult problem, we show that replication test scores can be used to develop an algorithm that approximates the optimal solution up to a logarithmic factor. The techniques presented in this work bridge the gap between the rigorous theoretical work on submodular optimization and simple, scalable heuristics that are useful in certain domains. In particular, our results establish that in many applications involving the selection and assignment of items, one can design algorithms that are intuitive and practically relevant with only a small loss in performance compared with the state-of-the-art ap

关键词： stochastic combinatorial optimization submodular functions welfare maximization test scores

来源：评论

学校读者我要写书评

暂无评论

A hybrid scatter search for the probabilistic traveling salesman problem

引用

COMPUTERS & OPERATIONS RESEARCH 2007年第10期34卷 2949-2963页

作者： Liu, Yu-Hsin Natl Chi Nan Univ Dept Civil Engn Puli 545 Nantou Hsien Taiwan

The probabilistic traveling salesman problem (PTSP) is an important theoretical and practical topic in the study of stochastic network problems. It provides researchers with a modeling framework for exploring the stochastic effects in routing problems. This paper focuses on developing the hybrid scatter search (HSS) by incorporating the nearest neighbor rule (NNR), threshold accepting (TA) and edge recombination (ER) crossover into a scatter search conceptual framework to solve the PTSP. A set of numerical experiments were conducted to test the validity of the HSS based on the test problems from Tang and Miller-Hooks' study. The numerical results showed that the HSS can effectively solve the PTSP in most of the tested cases in terms of objective function value. Moreover, the results also indicated that incorporating threshold accepting into the scatter search framework can further increase the computation efficiency while maintaining solution quality. These findings show the potential of the proposed HSS in solving the large-scale PTSP. (c) 2005 Elsevier Ltd. All rights reserved.

关键词： stochastic combinatorial optimization probabilistic traveling salesman problem scatter search threshold accepting edge recombination crossover

来源：评论

学校读者我要写书评

暂无评论

Designing e-commerce supply chains: a stochastic facility-location approach

引用

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2019年第2期26卷 507-528页

作者： Pages-Bernaus, Adela Ramalhinho, Helena Juan, Angel A. Calvet, Laura Univ Lleida Dept Math Lleida Spain Univ Pompeu Fabra Dept Econ & Business Barcelona Spain Open Univ Catalonia Dept Comp Sci IN3 Barcelona Spain

e-Commerce activity has been increasing during recent years, and this trend is expected to continue in the near future. e-Commerce practices are subject to uncertainty conditions and high variability in customers' demands. Considering these characteristics, we propose two facility-location models that represent alternative distribution policies in e-commerce (one based on outsourcing and another based on in-house distribution). These models take into account stochastic demands as well as more than one regular supplier per customer. Two methodologies are then introduced to solve these stochastic versions of the well-known capacitated facility-location problem. The first is a two-stage stochastic-programming approach that uses an exact solver. However, we show that this approach is not appropriate for tackle large-scale instances due to the computational effort required. Accordingly, we also introduce a "simheuristic" approach that is able to deal with large-scale instances in short computing times. An extensive set of benchmark instances contribute to illustrate the efficiency of our approach, as well as its potential utility in modern e-commerce practices.

关键词： e-commerce supply-chain management capacitated facility-location problem stochastic combinatorial optimization simheuristics stochastic programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：