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

IEEE/ACM International Conference on Computer Aided Design

作者： Flores, P Monteiro, J Costa, E IST INESC Lisbon Portugal

ISBN: (纸本)078039254X

In this paper we propose an exact algorithm that maximizes the sharing of partial terms in Multiple Constant Multiplication (MCM) operations. We model this problem as a Boolean network that covers all possible partial terms which may be used to generate the set of coefficients in the MCM instance. The PIs to this network are shifted versions of the MCM input. An AND gate represents an adder or a subtracter, i.e., an AND gate generates a new partial term. All partial terms that have the same numerical value are ORed together. There is a single output which is an AND over all the coefficients in the MCM. We cast this problem into a 0-1 Integer Linear Programming (ILP) problem by requiring that the output is asserted while minimizing the total number of AND gates that evaluate to one. A SAT-based solver is used to obtain the exact solution. We argue that for many real problems the size of the problem is within the capabilities of current SAT solvers. We present results using binary, CSD and MSD representations. Two main conclusions can be drawn from the results. One is that, in many cases, existing heuristics perform well, computing the best solution, or one close to it. The other is that the flexibility of the MSD representation does not have a significant impact in the solution obtained.

关键词： Boolean functions FIR filters adders digital arithmetic integer programming linear programming logic design logic gates AND gates Boolean network CSD representation MSD representation SAT-based solver binary representation exact algorithm integer adders Boolean algebra AND GATE Digital arithmetic binary representation Logic design FIR filters Boolean functions Logic gates Integer Programming linear programming Integer

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for identical parallel machine scheduling under scenarios 3

An exact algorithm for identical parallel machine scheduling...

引用

3rd World Conference on Mechanical Engineering and Intelligent Manufacturing (WCMEIM)

作者： Xie Han-Xin Wang Bing Shanghai Univ Sch Mechatron Engn & Automat Shanghai Peoples R China

ISBN: (纸本)9781665441094

This paper discusses an uncertain identical parallel machine scheduling problem. Discrete scenario set is used to describe the uncertain processing times in actual production conditions. Objective of this problem is to minimize the mean makespan among all scenarios, which reflects solution optimality in uncertain environment. The concept of mean scenario is defined in this paper and is used to transform the model of mean makespan under scenarios into traditional deterministic identical parallel machine problem. The cutting plane algorithm is used on the basis of the mean scenario to solve the problem. The developed algorithm was applied in extensive test cases, involving different sizes and parameters. The computational results show that this proposed algorithm can solve this parallel machine model in reasonable time and can be applied in practical problems.

关键词： manufacturing discrete scenarios identical parallel machine scheduling cutting plane algorithm exact algorithm

来源：评论

学校读者我要写书评

暂无评论

Hybrid Approaches based on Simulated Annealing and an exact algorithm for Mixed Integer Programming Problems

Hybrid Approaches based on Simulated Annealing and an Exact ...

引用

3rd International Conference on Networking and Computing (ICNC)

作者： Tamaki, Keitaro Tengan, Takeshi Nakamura, Morikazu Univ Ryukyus Grad Sch Sci & Eng Nishihara Okinawa 9030213 Japan Meio Univ Fac Int Studies Okinawa 9058585 Japan Univ Ryukyus Dept Informat Engn Okinawa 9030213 Japan

ISBN: (纸本)9780769548937;9781467346245

This paper proposes two hybrid approaches based on the exact algorithm and metaheuristic, simulated annealing, for mixed integer programming problems. The first algorithm tries to control the tradeoff between the computation time and the solution quality by reducing the number of variables of the instances to be solved by the exact algorithm. The variable reduction is performed on the basis of searching by simulated annealing in the hybrid algorithm. The second hybrid algorithm considers not only the problem size reduction but also the computation time constraint of searching for the exact algorithm. The experimental evaluation shows that the exact algorithm and SA complement each other and the second hybrid algorithm performs better than the others.

关键词： Combinatorial Optimization Mixed Integer Programming Hybrid Method exact algorithm Metaheuristics Simulated Annealing

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for two-dimensional cutting problems based on multi-level pattern

引用

GRAPHICAL MODELS 2024年 133卷

作者： Pan, Weiping Hainan Vocat Univ Sci & Technol Coll Informat Engn Haikou 571126 Peoples R China Dalian Maritime Univ Coll Transportat Engn Dalian 116026 Peoples R China

A multi-level pattern is proposed for the unconstrained two-dimensional cutting problems of rectangular items, and an exact generation algorithm is constructed. The arrangement of rectangular items with the same type in multiple rows and columns is referred to as a 0-level pattern. An n-level pattern is the horizontal or vertical combination of an n-1 level pattern with a pattern whose level will not exceed n-1. The generation algorithm of multi-level pattern is constructed on the base of dynamic programming, and the multi-level patterns with various sizes are generated with increased level order. The normal size is chosen to reduce unnecessary computation in the algorithm. Three sets of benchmark instances and one set of random production instance from the literatures are used for comparison. Comparing to the exact algorithm in the literature, the results in this paper are equivalent, but the computation time is shorter. Comparing to heuristic algorithms in literatures, the results in this paper are better and the computation time is still good enough for practical applications.

关键词： Two-dimensional cutting Guillotine cutting Dynamic programming exact algorithm

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for the Euclidean k-Steiner tree problem

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2024年 121卷

作者： Brazil, Marcus Hendriksen, Michael Lee, Jae Payne, Michael S. Ras, Charl Thomas, Doreen Univ Melbourne Dept Elect & Elect Engn Melbourne Australia Univ Melbourne Sch Math & Stat Melbourne Australia La Trobe Univ Dept Math & Phys Sci Melbourne Australia Univ Melbourne Dept Mech Engn Melbourne Australia

The Euclidean k-Steiner tree problem asks for a minimum-cost network connecting n given points in the plane, allowing at most k additional nodes referred to as Steiner points. In the classical Steiner tree problem in which there is no restriction on the number of nodes, every Steiner point must be of degree 3. The k-Steiner problem differs in that Steiner points of degree 4 may be included in an optimal solution. This simple change leads to a number of complexities when attempting to create a generation algorithm for optimal k-Steiner trees, which has proven to be a powerful component of the flagship algorithm, namely GeoSteiner, for solving the classical Steiner tree problem. In the present paper we firstly extend the basic framework of GeoSteiner's generation algorithm to include degree-4 Steiner points. We then introduce a number of novel results restricting the structural and geometric properties of optimal k-Steiner trees, and then show how these properties may be used as topological pruning methods underpinning our generation algorithm. Finally, we present experimental data to show the effectiveness of our pruning methods in reducing the number of sub-optimal solution topologies. (c) 2024 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

关键词： 1-Steiner k-Steiner Steiner tree exact algorithm

来源：评论

学校读者我要写书评

暂无评论

Using graph models to find transcription factor modules: the hitting set problem and an exact algorithm

引用

algorithmS FOR MOLECULAR BIOLOGY 2013年第1期8卷 2-2页

作者： Lu, Songjian Lu, Xinghua Univ Pittsburgh Dept Biomed Informat Pittsburgh PA 15219 USA

Systematically perturbing a cellular system and monitoring the effects of the perturbations on gene expression provide a powerful approach to study signal transduction in gene expression systems. A critical step of revealing a signal transduction pathway regulating gene expression is to identify transcription factors transmitting signals in the system. In this paper, we address the task of identifying modules of cooperative transcription factors based on results derived from systems-biology experiments at two levels: First, a graph algorithm is developed to identify a minimum set of co-operative TFs that covers the differentially expressed genes under each systematic perturbation. Second, using a clique-finding approach, modules of TFs that tend to consistently cooperate together under various perturbations are further identified. Our results indicate that this approach is capable of identifying many known TF modules based on the individual experiment;thus we provide a novel graph-based method of identifying context-specific and highly reused TF-modules.

关键词： Time Complexity Bipartite Graph Minimum Weight exact algorithm Multiple Instance

来源：评论

学校读者我要写书评

暂无评论

exact formulations and algorithm for the train timetabling problem with dynamic demand

引用

COMPUTERS & OPERATIONS RESEARCH 2014年 44卷 66-74页

作者： Barrena, Eva Canca, David Coelho, Leandro C. Laporte, Gilbert Interuniv Res Ctr Network Enterprise Logist & Tra Quebec City PQ Canada HEC Montreal Montreal PQ H3T 2A7 Canada Univ Seville Sch Engn Seville 41092 Spain Univ Laval Fac Sci Adm Quebec City PQ G1K 7P4 Canada

In this paper we study the design and optimization of train timetabling adapted to a dynamic demand environment. This problem arises in rapid train services which are common in most important cities. We present three formulations for the problem, with the aim of minimizing passenger average waiting time. The most intuitive model would consider binary variables representing train departure times but it yields to non-linear objective function. Instead, we introduce flow variables, which allow a linear representation of the objective function. We provide incremental improvements on these formulations, which allows us to evaluate and compare the benefits and disadvantages of each modification. We present a branch-and-cut algorithm applicable to all formulations. Through extensive computational experiments on several instances derived from real data provided by the Madrid Metropolitan Railway, we show the advantages of designing a timetable adapted to the demand pattern, as opposed to a regular timetable. We also perform an extensive computational comparison of all linear formulations in terms of size, solution quality and running time. (C) 2013 Elsevier Ltd. All rights reserved.

关键词： Train timetabling Dynamic demand Regular timetable exact algorithm Branch-and-cut

来源：评论

学校读者我要写书评

暂无评论

A piecewise trajectory optimization model for connected automated vehicles: exact optimization algorithm and queue propagation analysis

引用

TRANSPORTATION RESEARCH PART B-METHODOLOGICAL 2018年 118卷 429-456页

作者： Li, Xiaopeng Ghiasi, Amir Xu, Zhigang Qu, Xiaobo Univ S Florida Dept Civil & Environm Engn Tampa FL 33620 USA Changan Univ Sch Informat Engn Xian 710064 Shaanxi Peoples R China Chalmers Univ Technol Dept Architecture & Civil Engn SE-41296 Gothenburg Sweden

This paper formulates a simplified traffic smoothing model for guiding movements of connected automated vehicles on a general one-lane highway segment. Adapted from the shooting heuristic proposed by Zhou et al. (2017) and Ma et al. (2017), this model confines each vehicle's trajectory as a piecewise quadratic function with no more than five pieces and lets all trajectories in the same platoon share identical acceleration and deceleration rates. Similar to the shooting heuristic, the proposed simplified model is able to control the overall smoothness of a platoon of connected automated vehicles and approximately optimize traffic performance in terms of fuel efficiency and driving comfort. While the shooting heuristic relies on numerical meta-heuristic algorithms that cannot ensure solution optimality, we discover a set of elegant theoretical properties for the general objective function and the associated constraints in the proposed simplified model, and consequentially propose an efficient analytical algorithm for solving this problem to the exact optimum. Interestingly, this exact algorithm has intuitive physical interpretations, i.e., stretching the transitional parts of the trajectories (i.e., parts with acceleration and deceleration adjustments) as far as they reach the upstream end of the investigated segment, and then balancing the acceleration and deceleration magnitudes as close as possible. This analytical exact model can be considered as a core module to a range of general trajectory optimization problems at various infrastructure settings. Numerical examples reveal that this exact algorithm has much more efficient computational performance and the same or better solution quality compared with the previously proposed shooting heuristic. These examples also illustrate how to apply this model to CAV control problems on signalized segments and at non-stop intersections. Further, we study a homogeneous special case of this model and analytically formulate the

关键词： Connected automated vehicles Trajectory optimization Traffic smoothing exact algorithm Shooting heuristic Fuel consumption Driving comfort Signalized intersection Non-stop intersection

来源：评论

学校读者我要写书评

暂无评论

An exact Quadratic algorithm for the Shortest Tree Transformation

引用

DOKLADY MATHEMATICS 2024年第2期110卷 373-378页

作者： Gorbunov, K. Yu. Lyubetsky, V. A. Russian Acad Sci Kharkevich Inst Inst Informat Transmiss Problems Moscow Russia Lomonosov Moscow State Univ Moscow Russia

The article proposes a new exact algorithm of quadratic complexity that solves the problem of the shortest transformation ("alignment") of one weighted tree into another, taking into account arbitrary costs of operations on trees. Three operations are considered: adding vertex deletions to an edge or root of a tree and shifting a subtree with deletions.

关键词： discrete optimization shortest tree transformation operations on a tree operation cost exact algorithm quadratic complexity algorithm tree alignment

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：