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

PMS5: an efficient exact algorithm for the (l, d)-motif finding problem

BMC BIOINFORMATICS 2011年第1期12卷 1-10页

作者： Dinh, Hieu Rajasekaran, Sanguthevar Kundeti, Vamsi K. Univ Connecticut Dept CSE Storrs CT 06269 USA

Background: Motifs are patterns found in biological sequences that are vital for understanding gene function, human disease, drug design, etc. They are helpful in finding transcriptional regulatory elements, transcription factor binding sites, and so on. As a result, the problem of identifying motifs is very crucial in biology. Results: Many facets of the motif search problem have been identified in the literature. One of them is (l, d)-motif search (or Planted Motif Search (PMS)). The PMS problem has been well investigated and shown to be NP-hard. Any algorithm for PMS that always finds all the (l, d)-motifs on a given input set is called an exact algorithm. In this paper we focus on exact algorithms only. All the known exact algorithms for PMS take exponential time in some of the underlying parameters in the worst case scenario. But it does not mean that we cannot design exact algorithms for solving practical instances within a reasonable amount of time. In this paper, we propose a fast algorithm that can solve the well-known challenging instances of PMS: (21, 8) and (23, 9). No prior exact algorithm could solve these instances. In particular, our proposed algorithm takes about 10 hours on the challenging instance (21, 8) and about 54 hours on the challenging instance (23, 9). The algorithm has been run on a single 2.4GHz PC with 3GB RAM. The implementation of PMS5 is freely available on the web at http://***/downloads/***. Conclusions: We present an efficient algorithm PMS5 that uses some novel ideas and combines them with well-known algorithm PMS1 and PMSPrune. PMS5 can tackle the large challenging instances (21, 8) and (23, 9). Therefore, we hope that PMS5 will help biologists discover longer motifs in the futures.

关键词： Integer Linear Program exact algorithm Approximate algorithm Input String Motif Search

来源：评论

学校读者我要写书评

暂无评论

CORAL: An exact algorithm for the Multidimensional Knapsack Problem

引用

INFORMS JOURNAL ON COMPUTING 2012年第3期24卷 399-415页

作者： Mansini, Renata Speranza, M. Grazia Univ Brescia Dept Informat Engn I-25123 Brescia Italy Univ Brescia Dept Quantitat Methods I-25122 Brescia Italy

The multidimensional knapsack problem (MKP) is a well-known, strongly NP-hard problem and one of the most challenging problems in the class of the knapsack problems. In the last few years, it has been a favorite playground for metaheuristics, but very few contributions have appeared on exact methods. In this paper we introduce an exact approach based on the optimal solution of subproblems limited to a subset of variables. Each subproblem is faced through a recursive variable-fixing process that continues until the number of variables decreases below a given threshold (restricted core problem). The solution space of the restricted core problem is split into subspaces, each containing solutions of a given cardinality. Each subspace is then explored with a branch-and-bound algorithm. Pruning conditions are introduced to improve the efficiency of the branch-and-bound routine. In all the tested instances, the proposed method was shown to be, on average, more efficient than the recent branch-and-bound method proposed by Vimont et al. [Vimont, Y., S. Boussier, M. Vasquez. 2008. Reduced costs propagation in an efficient implicit enumeration for the 0-1 multidimensional knapsack problem. J. Combin. Optim. 15(2) 165-178] and CPLEX 10. We were able to improve the best-known solutions for some of the largest and most difficult instances of the OR-LIBRARY data set [Chu, P. C., J. E. Beasley. 1998. A genetic algorithm for the multidimensional knapsack problem. J. Heuristics 4(1) 63-86].

关键词： multidimensional knapsack problem exact algorithm reduced costs recursive variable fixing cardinality constraint

来源：评论

学校读者我要写书评

暂无评论

exact algorithm for One Cardinality-Weighted 2-Partitioning Problem of a Sequence 1

引用

13th International Conference on Learning and Intelligent Optimization (LION)

作者： Kel'manov, Alexander Khamidullin, Sergey Panasenko, Anna Sobolev Inst Math 4 Koptyug Ave Novosibirsk 630090 Russia Novosibirsk State Univ 2 Pirogova St Novosibirsk 630090 Russia

ISBN: (数字)9783030386290

ISBN: (纸本)9783030386290;9783030386283

We consider a problem of 2-partitioning a finite sequence of points in Euclidean space into two clusters of the given sizes with some additional constraints. The solution criterion is the minimum of the sum (over both clusters) of weighted intracluster sums of squared distances between the elements of each cluster and its center. The weights of the intracluster sums are equal to the cardinalities of the desired clusters. The center of one cluster is given as input, while the center of the other one is unknown and is determined as a geometric center, i.e. as a point of space equal to the mean of the cluster elements. The following constraints hold: the difference between the indices of two subsequent points included in the first cluster is bounded from above and below by given some constants. It is shown that the considered problem is the strongly NP-hard one. An exact algorithm is proposed for the case of integer-valued input of the problem. This algorithm has a pseudopolynomial running time if the space dimension is fixed.

关键词： Euclidean space Sequence of points Weighted 2-partition Quadratic variation NP-hard problem Integer coordinates exact algorithm Fixed space dimension Pseudopolynomial time

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for the multi-period inspector scheduling problem

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2020年 145卷

作者： Shen, Huaxiao Shu, Shengnan Qin, Hu Wu, Qinghua Sun Yat Sen Univ Guangzhou 510275 Peoples R China Hong Kong Polytech Univ Dept Logist & Maritime Studies Kowloon Hong Kong Peoples R China Huazhong Univ Sci & Technol Sch Management Wuhan 430074 Peoples R China

In this paper, we study the multi-period inspector scheduling problem (MPISP). This problem aims to determine a set of routes for a team of inspectors performing inspection jobs in different locations across multiple days, with the objective of maximizing the total workloads that the inspectors undertake. Since an inspector can only perform inspections or travel during working periods and rest at other times, a route for an inspector is divided into several segments. This characteristic, on the one hand, differentiates the MPISP from many routing problems in the literature;on the other hand, however, makes the routing decisions more complicated and challenging. To solve the MPISP, we first formulate it into a set-packing model and then propose an exact branchand-price algorithm. In particular, we design a tailored label-setting algorithm for the pricing subproblem, which is a variant of the elementary shortest path problem with resource constraints. Moreover, we implement some acceleration techniques, such as bidirectional search, label pruning, decremental search space relaxation, and heuristic column generator. Extensive computational experiments were conducted on a set of benchmark instances, and the results have demonstrated the effectiveness of the proposed algorithm.

关键词： Routing Inspector scheduling problem Multi-period exact algorithm Branch-and-price Label-setting algorithm

来源：评论

学校读者我要写书评

暂无评论

A refined exact algorithm for Edge Dominating Set

引用

THEORETICAL COMPUTER SCIENCE 2014年第P2期560卷 207-216页

作者： Xiao, Mingyu Nagarnochi, Hiroshi Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 611731 Peoples R China Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Sakyo Ku Kyoto 6068501 Japan

In this paper, we present a new exact algorithm for the EDGE DOMINATING SET problem, and analyze its running time by the Measure and Conquer method. Our algorithm runs in 1.3160(n)n(0(1)) time for a graph with n vertices, which is the currently fastest known time for the EDGE DOMINATING SET problem. By designing new branching rules based upon conceptually simple local structures, which we call clique-producing vertices and cycles, we obtain an algorithm that is simpler than the previously fastest known algorithm and has an improved time bound as well. (C) 2014 Elsevier B.V. All rights reserved.

关键词： exact algorithm Edge Dominating Set Measure and Conquer

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for the Two-Dimensional Stage-Unrestricted Guillotine Cutting/Packing Decision Problem

引用

INFORMS JOURNAL ON COMPUTING 2016年第4期28卷 703-720页

作者： Fleszar, Krzysztof Amer Univ Beirut Suliman S Olayan Sch Business Beirut 11072020 Lebanon

We propose a new exact algorithm for the two-dimensional stage-unrestricted guillotine cutting/packing decision problem, which asks if a set of rectangular items can be cut from a single stock rectangle using guillotine cuts only, with fixed item orientation or with 90-degree item rotation. Our algorithm constructs patterns of items by means of horizontal and vertical builds. To speed up the algorithm and reduce its memory requirement, patterns are constructed in the order of nondecreasing waste, the patterns that use the same subset of items are grouped together, and dominated patterns in each group are discarded. Moreover, a heuristic capable of completing a partial pattern is repeatedly used during the algorithm to quickly determine a feasible solution. Furthermore, the algorithm tries to prove infeasibility with a subset of items before considering all items. We test our algorithm on benchmark instances for the two-dimensional guillotine strip-cutting problem, which we solve by varying the strip height and testing with our algorithm whether a feasible solution exists. We show that our approach outperforms all previously proposed algorithms for the problem with fixed item orientation. Computational experiments for the problem with item rotation are also reported.

关键词： exact algorithm two-dimensional cutting/packing guillotine cuts rotation strip cutting

来源：评论

学校读者我要写书评

暂无评论

SOLVING THE MINIMUM INDEPENDENT DOMINATION SET PROBLEM IN GRAPHS BY exact algorithm AND GREEDY HEURISTIC

引用

RAIRO-OPERATIONS RESEARCH 2013年第3期47卷 199-221页

作者： Laforest, Christian Phan, Raksmey Univ Blaise Pascal CNRS UMR 6158 LIMOS F-63173 Aubiere France

In this paper we present a new approach to solve the Minimum Independent Dominating Set problem in general graphs which is one of the hardest optimization problem. We propose a method using a clique partition of the graph, partition that can be obtained greedily. We provide conditions under which our method has a better complexity than the complexity of the previously known algorithms. Based on our theoretical method, we design in the second part of this paper an efficient algorithm by including cuts in the search process. We then experiment it and show that it is able to solve almost all instances up to 50 vertices in reasonable time and some instances up to several hundreds of vertices. To go further and to treat larger graphs, we analyze a greedy heuristic. We show that it often gives good (sometimes optimal) results in large instances up to 60 000 vertices in less than 20 s. That sort of heuristic is a good approach to get an initial solution for our exact method. We also describe and analyze some of its worst cases.

关键词： Combinatorial optimization heuristics exact algorithm worst case analysis experimentations independent dominating set in graphs

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for wirelength optimal placements in VLSI design

引用

INTEGRATION-THE VLSI JOURNAL 2016年 52卷 355-366页

作者： Funke, J. Hougardy, S. Schneider, J. Univ Bremen Lehrstuhl Logist D-28359 Bremen Germany Univ Bonn Res Inst Discrete Math D-53113 Bonn Germany

We present a new algorithm designed to solve floorplanning problems optimally. More precisely, the algorithm finds solutions to rectangle packing problems which globally minimize wirelength and avoid given sets of blocked regions. We present the first optimal floorplans for 3 of the 5 intensely studied MCNC block packing instances and a significantly larger industrial instance with 27 rectangles and thousands of nets. Moreover, we show how to use the algorithm to place larger instances that cannot be solved optimally in reasonable runtime. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Floorplanning Placement Rectangle packing Wirelength minimization exact algorithm

来源：评论

学校读者我要写书评

暂无评论

A Fast exact algorithm for Deployment of Sensor Nodes for Internet of Things

引用

INFORMATION SYSTEMS FRONTIERS 2020年第4期22卷 829-842页

作者： Zheng, Qinghua Ya, Chutong Yang, Haijun Zhou, Jianhe Guangxi Univ Sci & Technol Sch Comp Sci Liuzhou 545006 Guangxi Peoples R China Univ Calif San Diego Jacobs Sch Engn San Diego CA 92093 USA Beihang Univ Sch Econ & Management Beijing 100191 Peoples R China Beihang Univ Beijing Adv Innovat Ctr Big Data & Brain Comp Beijing 100191 Peoples R China

The deployment problem of sensor nodes of Internet of things (IoT) can be abstracted as listing minimal dominating sets of a graph. The problem of listing all the minimal dominating sets in a graph can be converted to the problem of state space search among candidate vertex sets. The search and optimization technologies, such as the bidirectional search and branch cut, can be applied to solve the problem effectively. Our experiments show that the new algorithm can reduce the running time by at least an order of magnitude, compared to a state-of-the-art algorithm for listing all the minimal dominating sets.

关键词： Graph Minimal dominating set exact algorithm State space search

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for the precedence-constrained single-machine scheduling problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2013年第2期229卷 345-352页

作者： Tanaka, Shunji Sato, Shun Kyoto Univ Dept Elect Engn Nishikyo Ku Kyoto 6158510 Japan

This study proposes an efficient exact algorithm for the precedence-constrained single-machine scheduling problem to minimize total job completion cost where machine idle time is forbidden. The proposed algorithm is based on the SSDP (Successive Sublimation Dynamic Programming) method and is an extension of the authors' previous algorithms for the problem without precedence constraints. In this method, a lower bound is computed by solving a Lagrangian relaxation of the original problem via dynamic programming and then it is improved successively by adding constraints to the relaxation until the gap between the lower and upper bounds vanishes. Numerical experiments will show that the algorithm can solve all instances with up to 50 jobs of the precedence-constrained total weighted tardiness and total weighted earliness-tardiness problems, and most instances with 100 jobs of the former problem. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Scheduling Single-machine Precedence constraints exact algorithm Lagrangian relaxation Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：