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

Roundoff-Error-Free algorithms for Solving Linear Systems via Cholesky and LU Factorizations

INFORMS JOURNAL ON COMPUTING 2015年第4期27卷 677-689页

作者： Escobedo, Adolfo R. Moreno-Centeno, Erick Texas A&M Univ Dept Ind & Syst Engn College Stn TX 77843 USA

LU and Cholesky factorizations are computational tools for efficiently solving linear systems that play a central role in solving linear programs and several other classes of mathematical programs. In many documented cases, however, the roundoff errors accrued during the construction and implementation of these factorizations lead to the misclassification of feasible problems as infeasible and vice versa. Hence, reducing these roundoff errors or eliminating them altogether is imperative to guarantee the correctness of the solutions provided by optimization solvers. To achieve this goal without having to use rational arithmetic, we introduce two roundoff-error-free factorizations that require storing the same number of individual elements and performing a similar number of operations as the traditional LU and Cholesky factorizations. Additionally, we present supplementary roundoff-error-free forward and backward substitution algorithms, thereby providing a complete tool set for solving systems of linear equations exactly and efficiently. An important property shared by the featured factorizations and substitution algorithms is that their individual coefficients' maximum word length-i.e., the maximum number of digits required for expression-is bounded polynomially. Unlike the rational arithmetic methods used in practice to solve linear systems exactly, however, the algorithms herein presented do not require any gcd calculations to bound the entries' word length. We also derive various other related theoretical results, including the total computational complexity of all the roundoff-error-free processes herein presented.

关键词： exact mathematical programming exact algorithms matrix factorizations roundoff errors solving linear systems

来源：评论

学校读者我要写书评

暂无评论

On the empirical time complexity of finding optimal solutions vs proving optimality for Euclidean TSP instances

引用

OPTIMIZATION LETTERS 2015年第6期9卷 1247-1254页

作者： Hoos, Holger H. Stutzle, Thomas Univ British Columbia Dept Comp Sci Vancouver BC V6T 1W5 Canada Univ Libre Bruxelles IRIDIA CoDE Brussels Belgium

We investigate the empirical performance of the long-standing state-of-the-art exact TSP solver Concorde on various classes of Euclidean TSP instances and show that, surprisingly, the time spent until the first optimal solution is found accounts for a large fraction of Concorde's overall running time. This finding holds for the widely studied random uniform Euclidean (RUE) instances as well as for several other widely studied sets of Euclidean TSP instances. On RUE instances, the median fraction of Concorde's total running time spent until an optimal solution is found ranges from 0.77 for to 0.97 for;on TSPLIB, National and VLSI instances, we pegged it at 0.86, 0.74 and 0.61, respectively, with a tendency of even smaller values for larger instances.

关键词： TSP Empirical complexity exact algorithms

来源：评论

学校读者我要写书评

暂无评论

A review on algorithms for maximum clique problems

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2015年第3期242卷 693-709页

作者： Wu, Qinghua Hao, Jin-Kao Huazhong Univ Sci & Technol Sch Management Wuhan 430074 Peoples R China Univ Angers LERIA F-49045 Angers 1 France

The maximum clique problem (MCP) is to determine in a graph a clique (i.e., a complete subgraph) of maximum cardinality. The MCP is notable for its capability of modeling other combinatorial problems and real-world applications. As one of the most studied NP-hard problems, many algorithms are available in the literature and new methods are continually being proposed. Given that the two existing surveys on the MCP date back to 1994 and 1999 respectively, one primary goal of this paper is to provide an updated and comprehensive review on both exact and heuristic MCP algorithms, with a special focus on recent developments. To be informative, we identify the general framework followed by these algorithms and pinpoint the key ingredients that make them successful. By classifying the main search strategies and putting forward the critical elements of the most relevant clique methods, this review intends to encourage future development of more powerful methods and motivate new applications of the clique approaches. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Maximum clique problems exact algorithms Heuristics Applications

来源：评论

学校读者我要写书评

暂无评论

DETECTING AND COUNTING SMALL PATTERN GRAPHS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2015年第3期29卷 1322-1339页

作者： Floderus, Peter Kowaluk, Miroslaw Lingas, Andrzej Lundell, Eva-Marta Lund Univ Ctr Math Sci S-22100 Lund Sweden Warsaw Univ Inst Informat Warsaw Poland Lund Univ Dept Comp Sci S-22100 Lund Sweden

We study the induced subgraph isomorphism problem and the general subgraph isomorphism problem for small pattern graphs. We present a new general method for detecting induced subgraphs of a host graph isomorphic to a fixed pattern graph by reduction to polynomial testing for nonidentity with zero over a field of finite characteristic. It yields new upper time bounds for several pattern graphs on five vertices and provides an alternative combinatorial method for the majority of pattern graphs on four and three vertices. Since our method avoids the large overhead of fast matrix multiplication, it can be of practical interest even for larger pattern graphs. Next, we derive new upper time bounds on counting the number of isomorphisms between a fixed pattern graph with an independent set of size s and a subgraph of the host graph. We also consider a weighted version of the counting problem, when one counts the number of isomorphisms between the pattern graph and lightest subgraphs, providing a slightly slower combinatorial algorithm.

关键词： subgraph and induced subgraph isomorphism counting and detection of subgraphs polynomial testing exact algorithms randomized algorithms rectangular matrix multiplication

来源：评论

学校读者我要写书评

暂无评论

exact algorithm for matrix-based project planning problems

引用

EXPERT SYSTEMS WITH APPLICATIONS 2015年第9期42卷 4460-4473页

作者： Kosztyan, Zsolt T. Univ Pannonia Dept Quantitat Methods Veszprem Hungary

This paper proposes a new matrix-based project planning method that takes into consideration task importance or probability of completions thus determines and ranks the importance or probability of possible project scenarios and project structures. The proposed algorithm is fast, aims to select the most important project scenarios or the least cost/time demanding project structures. The algorithm is generic, can host several types of goals dictated by the characteristics of project management and as such can be the fundamental element of a project expert- and decision-making system. (C) 2015 Elsevier Ltd. All rights reserved.

关键词： Project planning methods Decision-making tools exact algorithms Supporting traditional and agile project managements

来源：评论

学校读者我要写书评

暂无评论

A literature review on the vehicle routing problem with multiple depots

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2015年 79卷 115-129页

作者： Montoya-Torres, Jairo R. Lopez Franco, Julian Nieto Isaza, Santiago Felizzola Jimenez, Heriberto Herazo-Padilla, Nilson Univ La Sabana Escuela Int Ciencias Econ & Adm Chia Cundinamarca Colombia Engn & Consulting SAS Bogota DC Colombia Univ Norte Dept Ingn Ind Barranquilla Atlantico Colombia Univ La Sabana Dept Ingn Ind Bogota DC Colombia Univ Costa Dept Ingn Ind Barranquilla Colombia Fdn Ctr Invest Modelac Empresarial Caribe Barranquilla Colombia

In this paper, we present a state-of-the-art survey on the vehicle routing problem with multiple depots (MDVRP). Our review considered papers published between 1988 and 2014, in which several variants of the model are studied: time windows, split delivery, heterogeneous fleet, periodic deliveries, and pickup and delivery. The review also classifies the approaches according to the single or multiple objectives that are optimized. Some lines for further research are presented as well. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： Vehicle routing Multiple depots exact algorithms Heuristics Survey

来源：评论

学校读者我要写书评

暂无评论

An overview of curriculum-based course timetabling

引用

TOP 2015年第2期23卷 313-349页

作者： Bettinelli, Andrea Cacchiani, Valentina Roberti, Roberto Toth, Paolo Univ Bologna DEI I-40136 Bologna Italy Tech Univ Denmark Dept Transport DK-2800 Lyngby Denmark

In 2007, the Second International Timetabling Competition (ITC-2007) has been organized and a formal definition of the Curriculum-Based Course Timetabling (CB-CTT) problem has been given, by taking into account several real-world constraints and objectives while keeping the problem general. CB-CTT consists of finding the best weekly assignment of university course lectures to rooms and time periods. A feasible schedule must satisfy a set of hard constraints and must also take into account a set of soft constraints, whose violation produces penalty terms to be minimized in the objective function. From ITC-2007, many researchers have developed advanced models and methods to solve CB-CTT. This survey is devoted to review the main works on the topic, with focus on mathematical models, lower bounds, and exact and heuristic algorithms. Besides giving an overview of these approaches, we highlight interesting extensions that could make the study of CB-CTT even more challenging and closer to reality.

关键词： University timetabling Curriculum-based course timetabling Survey Models exact algorithms Heuristic algorithms

来源：评论

学校读者我要写书评

暂无评论

Affinity Propagation and Uncapacitated Facility Location Problems

引用

JOURNAL OF CLASSIFICATION 2015年第3期32卷 443-480页

作者： Brusco, Michael J. Steinley, Douglas Florida State Univ Coll Business Tallahassee FL 32306 USA Univ Missouri Dept Psychol Sci Columbia MO 65203 USA

One of the most important distinctions that must be made in clustering research is the difference between models (or problems) and the methods for solving those problems. Nowhere is this more evident than with the evaluation of the popular affinity propagation algorithm (apcluster.m), which is a MATLAB implementation of a neural clustering method that has received significant attention in the biological sciences and other disciplines. Several authors have undertaken comparisons of apcluster.m with methods designed for models that fall within the class of uncapacitated facility location problems (UFLPs). These comparative models include the p-center (or K-center) model and, more importantly, the p-median (or K-median) model. The results across studies are conflicting and clouded by the fact that, although similar, the optimization model underlying apcluster.m is slightly different from the p-median model and appreciably different from the pcenter model. In this paper, we clarify that apcluster.m is actually a heuristic for a 'maximization version' of another model in the class of UFLPs, which is known as the simple plant location problem (SPLP). An exact method for the SPLP is described, and the apcluster.m program is compared to a fast heuristic procedure (sasplp.m) in both a simulation experiment and across numerous datasets from the literature. Although the exact method is the preferred approach when computationally feasible, both apcluster.m and sasplp.m are efficient and effective heuristic approaches, with the latter slightly outperforming the former in most instances.

关键词： Clustering exact algorithms Heuristics Simple plant location problem Affinity propagation

来源：评论

学校读者我要写书评

暂无评论

An exact Algorithm for the Two-Mode KL-Means Partitioning Problem

引用

JOURNAL OF CLASSIFICATION 2015年第3期32卷 481-515页

作者： Brusco, Michael J. Doreian, Patrick Florida State Univ Coll Business Tallahassee FL 32306 USA Univ Ljubljana Fac Social Sci Ljubljana Slovenia Univ Pittsburgh Dept Sociol Pittsburgh PA USA

Two-mode partitioning applications are increasingly common in the physical and social sciences with a variety of models and methods spanning these applications. Two-mode KL-means partitioning (TMKLMP) is one type of two-mode partitioning model with a conceptual appeal that stems largely from the fact that it is a generalization of the ubiquitous (one-mode) K-means clustering problem. A number of heuristic methods have been proposed for TMKLMP, ranging from a two-mode version of the K-means heuristic to metaheuristic approaches based on simulated annealing, genetic algorithms, variable neighborhood search, fuzzy steps, and tabu search. We present an exact algorithm for TMKLMP based on branch-and-bound programming and demonstrate its utility for the clustering of brand switching, manufacturing cell formation, and journal citation data. Although the proposed branchand-bound algorithm does not obviate the need for approximation methods for large two-mode data sets, it does provide a first step in the development of methods that afford a guarantee of globally-optimal solutions for TMKLMP.

关键词： Two-mode partitioning exact algorithms Branch-and-bound

来源：评论

学校读者我要写书评

暂无评论

Parallelizing exact motif finding algorithms on multi-core

引用

JOURNAL OF SUPERCOMPUTING 2014年第2期69卷 814-826页

作者： Abbas, Mostafa M. Bahig, Hazem M. Abouelhoda, Mohamed Mohie-Eldin, M. M. Qatar Univ Coll Engn KINDI Lab Comp Res Doha Qatar Sinai Univ Dept Basic Sci Fac Engn Al Arish Egypt Hail Univ Coll Comp Sci & Engn Comp Sci & Software Engn Dept Hail Saudi Arabia Ain Shams Univ Div Comp Sci Dept Math Fac Sci Cairo 11566 Egypt Cairo Univ Syst & Biomed Engn Dept Fac Engn Giza Egypt Nile Univ Ctr Informat Sci Giza Egypt Al Azhar Univ Fac Sci Dept Math Cairo Egypt

The motif finding problem is one of the important and challenging problems in bioinformatics. A variety of sequential algorithms have been proposed to find exact motifs, but the running time is still not suitable due to high computational complexity of finding motifs. In this paper we parallelize three efficient sequential algorithms which are HEPPMSprune, PMS5 and PMS6. We implement the algorithms on a Dual Quad-Core machine using openMP to measure the performance of each algorithm. Our experiment on simulated data show that: (1) the parallel PMS6 is faster than the other algorithms in case of challenging instances, while the parallel HEPPMSprune is faster than the other algorithms in most of solvable instances;(2) the scalability of parallel HEPPMSprune is linear for all instances, while the scalability of parallel PMS5 and PMS6 is linear in case of challenging instances only;(3) the memory used by HEPPMSprune is less than that of the other algorithms.

关键词： exact algorithms Motif finding Multi-core Challenging and solvable instances

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：