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

Index branch-and-bound algorithm for Lipschitz univariate global optimization with multiextremal constraints

JOURNAL OF GLOBAL OPTIMIZATION 2001年第3期21卷 317-341页

作者： Sergeyev, YD Famularo, D Pugliese, P Univ Calabria DEIS CNR ISI I-87036 Arcavacata Di Rende CS Italy Univ Nizhni Novgorod Software Dept Nizhnii Novgorod Russia

In this paper, Lipschitz univariate constrained global optimization problems where both the objective function and constraints can be multiextremal are considered. The constrained problem is reduced to a discontinuous unconstrained problem by the index scheme without introducing additional parameters or variables. A branch-and-bound method that does not use derivatives for solving the reduced problem is proposed. The method either determines the infeasibility of the original problem or finds lower and upper bounds for the global solution. Not all the constraints are evaluated during every iteration of the algorithm, providing a significant acceleration of the search. Convergence conditions of the new method are established. Extensive numerical experiments are presented.

关键词： global optimization multiextremal constraints branch-and-bound algorithms index scheme

来源：评论

学校读者我要写书评

暂无评论

An Adaptative Multi-GPU based branch-and-bound. A Case Study: the Flow-Shop Scheduling Problem

An Adaptative Multi-GPU based Branch-and-Bound. A Case Study...

引用

14th IEEE International Conference on High Performance Computing and Communications (HPCC) / IEEE 9th International Conference on Embedded Software and Systems (ICESS)

作者： Chakroun, I. Melab, N. Univ Lille 1 CNRS UMR 8022 LIFLINRIA Lille Nord Europe F-59655 Villeneuve Dascq France

ISBN: (纸本)9780769547497

Solving exactly Combinatorial Optimization Problems (COPs) using a branch-and-bound (B&B) algorithm requires a huge amount of computational resources. Therefore, we recently investigated designing B&B algorithms on top of graphics processing units (GPUs) using a parallel bounding model. The proposed model assumes parallelizing the evaluation of the lower bounds on pools of sub-problems. The results demonstrated that the size of the evaluated pool has a significant impact on the performance of B&B and that it depends strongly on the problem instance being solved. In this paper, we design an adaptative parallel B&B algorithm for solving permutation-based combinatorial optimization problems such as FSP (Flow-shop Scheduling Problem) on GPU accelerators. To do so, we propose a dynamic heuristic for parameter auto-tuning at runtime. Another challenge of this pioneering work 1 is to exploit larger degrees of parallelism by using the combined computational power of multiple GPU devices. The approach has been applied to the permutation flow-shop problem. Extensive experiments have been carried out on well-known FSP benchmarks using an Nvidia Tesla S1070 Computing System equipped with two Tesla T10 GPUs. Compared to a CPU-based execution, accelerations up to x105 are achieved for large problem instances.

关键词： branch-and-bound algorithms Multi-GPU Computing Parallel bounding Flow-Shop Scheduling Problem

来源：评论

学校读者我要写书评

暂无评论

A GPU-accelerated branch-and-bound Algorithm for the Flow-Shop Scheduling Problem

A GPU-accelerated Branch-and-Bound Algorithm for the Flow-Sh...

引用

IEEE International Conference on Cluster Computing

作者： Melab, N. Chakroun, I. Mezmaz, M. Tuyttens, D. Univ Lille 1 CNRS LIFL UMR 8022 F-59655 Villeneuve Dascq France Univ Mons Dept Math & OR Mons Belgium

ISBN: (纸本)9781467324229

branch-and-bound (B&B) algorithms are time-intensive tree-based exploration methods for solving to optimality combinatorial optimization problems. In this paper, we investigate the use of GPU computing as a major complementary way to speed up those methods. The focus is put on the bounding mechanism of B&B algorithms, which is the most time consuming part of their exploration process. We propose a parallel B&B algorithm based on a GPU-accelerated bounding model. The proposed approach concentrate on optimizing data access management to further improve the performance of the bounding mechanism which uses large and intermediate data sets that do not completely fit in GPU memory. Extensive experiments of the contribution have been carried out on well-known FSP benchmarks using an Nvidia Tesla C2050 GPU card. We compared the obtained performances to a single and a multi-threaded CPU-based execution. Accelerations up to x100 are achieved for large problem instances.

关键词： Massively Parallel Computing GPU Computing branch-and-bound algorithms Lower bounding Flow-Shop Scheduling

来源：评论

学校读者我要写书评

暂无评论

An efficient branch-and-bound strategy for subset vector autoregressive model selection

引用

JOURNAL OF ECONOMIC DYNAMICS & CONTROL 2008年第6期32卷 1949-1963页

作者： Gatu, Cristian Kontoghiorghes, Erricos J. Gilli, Manfred Winker, Peter VTT Tech Res Ctr Finland FI-02044 Espoo Finland Univ Cyprus Dept Publ & Business Adm Nicosia Cyprus Univ Geneva Dept Econometr CH-1211 Geneva 4 Switzerland Univ Giessen Fachbereich Wirtschafts Wissensch D-35390 Giessen Germany Alexandru Ioan Cuza Univ Fac Comp Sci Iasi Romania Univ London Birkbeck Coll Sch Comp Sci & Informat Syst London WC1E 7HX England

A computationally efficient branch-and-bound strategy for finding the subsets of the most statistically significant variables of a vector autoregressive (VAR) model from a given search subspace is proposed. Specifically, the candidate submodels are obtained by deleting columns from the coefficient matrices of the full-specified VAR process. The strategy is based on a regression tree and derives the best-subset VAR models without computing the whole tree. The branch-and-bound cutting test is based on monotone statistical selection criteria which are functions of the determinant of the estimated residual covariance matrix. Experimental results confirm the computational efficiency of the proposed algorithm. (C) 2007 Elsevier B.V. All rights reserved.

关键词： vector autoregressive model model selection branch-and-bound algorithms

来源：评论

学校读者我要写书评

暂无评论

Index branch-and-bound algorithm for Lipschitz univariate global optimization with multiextremal constraints

Index branch-and-bound algorithm for Lipschitz univariate gl...

引用

International Workshop on Global Optimization (GO 99)

作者： Sergeyev, YD Famularo, D Pugliese, P Univ Calabria DEIS CNR ISI I-87036 Arcavacata Di Rende CS Italy Univ Nizhni Novgorod Software Dept Nizhnii Novgorod Russia

关键词： global optimization multiextremal constraints branch-and-bound algorithms index scheme

来源：评论

学校读者我要写书评

暂无评论

algorithms for processing K-closest-pair queries in spatial databases

引用

DATA & KNOWLEDGE ENGINEERING 2004年第1期49卷 67-104页

作者： Corral, A Manolopoulos, Y Theodoridis, Y Vassilakopoulos, M Univ Almeria Dept Language & Computat Almeria 04120 Spain Univ Thessaloniki Dept Informat GR-54006 Thessaloniki Greece Univ Piraeus Dept Informat Piraeus 18534 Greece Inst Educ Technol Dept Informat Thessaloniki 54101 Greece

This paper addresses the problem of finding the K closest pairs between two spatial datasets (the so-called, K closest pairs query, K-CPQ), where each dataset is stored in an R-tree. There are two different techniques for solving this kind of distance-based query. The first technique is the incremental approach, which returns the output elements one-by-one in ascending order of distance. The second one is the non-incremental alternative, which returns the K elements of the result all together at the end of the algorithm. In this paper, based on distance functions between two MBRs in the multidimensional Euclidean space, we propose a pruning heuristic and two updating strategies for minimizing the pruning distance, and use them in the design of three non-incremental branch-and-bound algorithms for K-CPQ between spatial objects stored in two R-trees. Two of those approaches are recursive following a Depth-First searching strategy and one is iterative obeying a Best-First traversal policy. The plane-sweep method and the search ordering are used as optimization techniques for improving the naive approaches. Besides, a number of interesting extensions of the K-CPQ (K-Self-CPQ, Semi-CPQ, K-FPQ (the K-farthest pairs query), etc.) are discussed. An extensive performance study is also presented. This study is based on experiments performed with real datasets. A wide range of values for the basic parameters affecting the performance of the algorithms is examined in order to designate the most efficient algorithm for each setting of parameter values. Finally, an experimental study of the behavior of the proposed K-CPQ branch-and-bound algorithms in terms of scalability of the dataset size and the K value is also included. (C) 2003 Elsevier B.V. All rights reserved.

关键词： spatial databases branch-and-bound algorithms query processing R-tree distance join I/O and response time performance

来源：评论

学校读者我要写书评

暂无评论

Optimal solutions for the closest-string problem via integer programming

引用

INFORMS JOURNAL ON COMPUTING 2004年第4期16卷 419-429页

作者： Meneses, CN Lu, ZS Oliveira, CAS Pardalos, PM Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA

In this paper we study the closest-string problem (CSP), which can be defined as follows: Given a finite set J = {s(1),s(2),...,s(n)) of strings, each string with length m, find a center string t of length m minimizing d, such that for every string s(i) is an element of J, d(H)(t, s(i)) less than or equal to d. By d(H)(t, s(i)) we mean the Hamming distance between t and s(i). This is an NP-hard problem, with applications in molecular biology and coding theory Even though there are good approximation algorithms for this problem, and exact algorithms for instances with d constant, there are no studies trying to solve it exactly for the general case. In this paper we propose three integer-programming (IP) formulations and a heuristic, which is used to provide upper bounds on the value of an optimal solution. We report computational results of a branch-and-bound algorithm based on one of the IP formulations, and of the heuristic, executed over randomly generated instances. These results show that it is possible to solve CSP instances of moderate size to optimality.

关键词： closest-string problem computational biology mathematical programming branch-and-bound algorithms

来源：评论

学校读者我要写书评

暂无评论

Global optimization algorithm for the nonlinear sum of ratios problem

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2002年第1期112卷 1-29页

作者： Benson, HP Univ Florida Warrington Coll Business Adm Gainesville FL 32611 USA

This article presents a branch-and-bound algorithm for globally solving the nonlinear sum of ratios problem (P). The algorithm economizes the required computations by conducting the branch-and-bound search in R-p, rather than in R-n, where p is the number of ratios in the objective function of problem (P) and n is the number of decision variables in problem (P). To implement the algorithm, the main computations involve solving a sequence of convex programming problems for which standard algorithms are available.

关键词： global optimization sum of ratios fractional programming branch-and-bound algorithms

来源：评论

学校读者我要写书评

暂无评论

Progressive skyline computation in database systems

引用

ACM TRANSACTIONS ON DATABASE SYSTEMS 2005年第1期30卷 41-82页

作者： Papadias, D Tao, YF Fu, G Seeger, B Hong Kong Univ Sci & Technol Dept Comp Sci Hong Kong Hong Kong Peoples R China City Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China JP Morgan Chase New York NY 10172 USA Univ Marburg Dept Math & Comp Sci D-35032 Marburg Germany

The skyline of a d-dimensional dataset contains the points that are not dominated by any other point on all dimensions. Skyline computation has recently received considerable attention in the database community, especially for progressive methods that can quickly return the initial results without reading the entire database. All the existing algorithms, however, have some serious shortcomings which limit their applicability in practice. In this article we develop branch-and-bound skyline (BBS), an algorithm based on nearest-neighbor search, which is I/O optimal, that is, it performs a single access only to those nodes that may contain skyline points. BBS is simple to implement and supports all types of progressive processing (e.g., user preferences, arbitrary dimensionality, etc). Furthermore, we propose several interesting variations of skyline computation, and show how BBS can be applied for their efficient processing.

关键词： algorithms experimentation skyline query branch-and-bound algorithms multidimensional access methods

来源：评论

学校读者我要写书评

暂无评论

Two-machine flowshop scheduling with job class setups to minimize total flowtime

引用

COMPUTERS & OPERATIONS RESEARCH 2005年第11期32卷 2751-2770页

作者： Wang, XL Cheng, TCE Hong Kong Polytech Univ Dept Logist Kowloon Hong Kong Peoples R China Zhejiang Univ Coll Elect Engn Hangzhou Peoples R China

This paper studies the two-machine flowshop scheduling problem with job class setups to minimize the total flowtime. The jobs are classified into classes, and setup is required on a machine if it switches processing of jobs from one class to another class, but no setup s required if the jobs are from the same class. For some special cases, we derive a number of properties of the optimal solution, based on which we design heuristics and branch-and-bound algorithms to solve these problems. Computational results show that these algorithms are effective in yielding near-optimal or optimal solutions to the tested problems. (c) 2004 Elsevier Ltd. All rights reserved.

关键词： flowshop scheduling job class setups Heuristizs branch-and-bound algorithms total flowtime

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：