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

A refined exact algorithm for Edge Dominating Set

THEORETICAL COMPUTER SCIENCE 2014年第Part2期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 an identical parallel additive machine scheduling problem with multiple processing alternatives

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2022年第13期60卷 4070-4089页

作者： Kim, Jun Kim, Hyun-Jung Korea Inst Ind Technol Mfg Proc Platform R&D Dept Ansan South Korea Korea Adv Inst Sci & Technol Dept Ind & Syst Engn 291 Daehak ro Daejeon South Korea

This paper develops an exact algorithm for the identical parallel additive machine scheduling problem by considering multiple processing alternatives to minimise the makespan. This research is motivated from an idea of elevating flexibility of a manufacturing system by using additive machines, such as 3D printers. It becomes possible to produce a job in a different form;a job can be printed in a complete form or in separate parts. This problem is defined as a bi-level optimisation model in which its upper level problem is to determine a proper processing alternative for each product, and its lower level problem is to assign the parts that should be produced to the additive machines. An exact algorithm, which consists of the linear programming relaxation of a one-dimensional cutting stock problem, a branch-and-price algorithm, and a rescheduling algorithm, is proposed to find an optimal solution of the problem. The experimental results show that the computational time of the algorithm outperforms a commercial solver (CPLEX). By examining how the parts are comprised when the processing alternatives are optimally selected, some useful insights are derived for designing processing alternatives of products.

关键词： Additive manufacturing system parallel machine scheduling multiple processing alternatives minimization of makespan exact algorithm

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times

引用

COMPUTERS & OPERATIONS RESEARCH 2013年第1期40卷 344-352页

作者： Tanaka, Shunji Araki, Mituhiko Kyoto Univ Dept Elect Engn Nishikyo Ku Kyoto 6158510 Japan Matsue Coll Technol Matsue Shimane 6908518 Japan

This study proposes an exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times. The algorithm is an extension of the authors' previous algorithm for the single-machine scheduling problem without setup times, which is based on the SSDP (Successive Sublimation Dynamic Programming) method. In the first stage of the algorithm, the conjugate subgradient algorithm or the column generation algorithm is applied to a Lagrangian relaxation of the original problem to adjust multipliers. Then, in the second stage, constraints are successively added to the relaxation until the gap between lower and upper bounds becomes zero. The relaxation is solved by dynamic programming and unnecessary dynamic programming states are eliminated to suppress the increase of computation time and memory space. In this study a branching scheme is integrated into the algorithm to manage to solve hard instances. The proposed algorithm is applied to benchmark instances in the literature and almost all of them are optimally solved. (C) 2012 Elsevier Ltd. All rights reserved.

关键词： Single-machine total weighted tardiness problem Sequence-dependent setup times exact algorithm Lagrangian relaxation Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for the Generalized List T-Coloring Problem

引用

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2014年第3期16卷 77-94页

作者： Junosza-Szaniawski, Konstanty Rzazewski, Pawel Warsaw Univ Technol Fac Math & Informat Sci PL-00661 Warsaw Poland

The generalized list T-coloring is a common generalization of many graph coloring models, including classical coloring, L (p, q) -labeling, channel assignment and T-coloring. Every vertex from the input graph has a list of permitted labels. Moreover, every edge has a set of forbidden differences. We ask for a labeling of vertices of the input graph with natural numbers, in which every vertex gets a label from its list of permitted labels and the difference of labels of the endpoints of each edge does not belong to the set of forbidden differences of this edge. In this paper we present an exact algorithm solving this problem, running in time O* ((tau + 2)(n)), where tau is the maximum forbidden difference over all edges of the input graph and n is the number of its vertices. Moreover, we show how to improve this bound if the input graph has some special structure, e.g. a bounded maximum degree, no big induced stars or a perfect matching.

关键词： graph labeling exact algorithm T-coloring generalized list T-coloring channel assignment

来源：评论

学校读者我要写书评

暂无评论

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 the Arrow Placement Problem in Directed Graph Drawings

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2019年第11期E102A卷 1481-1489页

作者： Kido, Naoto Masuda, Sumio Yamaguchi, Kazuaki Kobe Univ Grad Sch Engn Kobe Hyogo 6578501 Japan ARISE Analyt Inc Kobe Hyogo Japan

We consider the problem of placing arrows, which indicate the direction of each edge in directed graph drawings, without making them overlap other arrows, vertices and edges as much as possible. The following two methods have been proposed for this problem. One is an exact algorithm for the case in which the position of each arrow is restricted to some discrete points. The other is a heuristic algorithm for the case in which the arrow is allowed to move continuously on each edge. In this paper, we assume that the arrow positions are not restricted to discrete points and propose an exact algorithm for the problem of finding an arrow placement such that (a) the weighted sum of the numbers of overlaps with edges, vertices and other arrows is minimized and (b) the sum of the distances between the arrows and their edges' terminal vertices is minimized as a secondary objective. The proposed method solves this problem by reducing it to a mixed integer linear programming problem. Since this is an exponential time algorithm, we add a simple procedure as preprocessing to reduce the running time. Experimental results show that the proposed method can find a better arrow placement than the previous methods and the procedure for reducing the running time is effective.

关键词： directed graph drawing arrow placement exact algorithm

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for the multi-trip vehicle routing and scheduling problem of pickup and delivery of customers to the airport

引用

TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW 2015年第Jan.期73卷 114-132页

作者： Tang, Jiafu Yu, Yang Li, Jia Dongbei Univ Finance & Econ Coll Management Sci & Engn Dalian 116025 Peoples R China Northeastern Univ Inst Syst Engn State Key Lab Synthet Automat Proc Ind Shenyang 110004 Peoples R China China Mobile Grp Liaoning Ltd Ctr Informat Technol Shenyang 110179 Peoples R China

Door-to-Door service of Pickup and Delivery of Customers to the Airport (D2PDCA) is a new service provided by certain Airline Ticket Sales Agencies (ATSAs) in China. This new service provides an attractive alternative way by picking up customer at this/her specified position and at any time he/she preferred and delivering to the airport more conveniently than airport shuttle and thus earn high customer service quality. Compared with the single-trip mode, the multi-trip mode of D2PDCA (MTM-D2PDCA) service can reduce travel distances, the number of vehicles required and the operating cost. To obtain the exact solution of the MTM-D2PDCA problem, we propose a novel, exact algorithm based on the trip-chain-oriented set-partitioning (TCO-SP) model, where a trip-chain represents multiple trips made by a specific vehicle. In the exact algorithm, we propose an improved label-correcting method to remove infeasible trip-chains quickly and thus speed the search process. Based on the feasible trip-chains, the MTM-D2PDCA problem is formulated as the novel TCO-SP model, which can be solved exactly by the optimization software CPLEX. In addition, we present several mathematical insights into the relationship between the number of trip-chains and the number of local optimal trips that are applicable in both theory and practice. Extensive experiments are conducted to illustrate the application of the model and demonstrate the cost savings of the MTM-D2PDCA mode over the single-trip mode and provide managerial insights into successfully operating a MTM-D2PDCA service. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： Vehicle routing and scheduling problem Multi-trip Trip-chain exact algorithm Set-partitioning

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for minimizing resource availability costs in project scheduling

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2010年第3期206卷 562-568页

作者： Rodrigues, Savio B. Yamashita, Denise S. Univ Fed Sao Carlos Dept Math BR-13565905 Sao Carlos SP Brazil Univ Fed Sao Carlos Dept Prod Engn BR-13565905 Sao Carlos SP Brazil

A new exact algorithm that solves the Resource Availability Cost Problem (RACP) in project scheduling is shown to yield a significant improvement over the existing algorithm in the literature. The new algorithm consists of a hybrid method where an initial feasible solution is found heuristically. The branching scheme solves a Resource-Constrained Project Scheduling Problem (RCPSP) at each node where the resources of the RACP are fixed. The knowledge of previously solved RCPSPs is used to produce cuts in the search tree. A worst-case-performance theorem is established for this new algorithm. Experiments are performed on instances adapted from the PSPLIB database. The new algorithm can be used to minimize any resource availability cost problem once a procedure for the underlying resource-constrained problem is available. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Project scheduling Resource availability exact algorithm

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for sparse matrix bipartitioning

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2015年 85卷 79-90页

作者： Pelt, Daniel M. Bisseling, Rob H. Ctr Wiskunde & Informat Sci Comp Grp NL-1090 GB Amsterdam Netherlands Univ Utrecht Math Inst NL-3508 TA Utrecht Netherlands

The sparse matrix partitioning problem arises when minimizing communication in parallel sparse matrix vector multiplications. Since the problem is NP-hard, heuristics are usually employed to find solutions. Here, we present a purely combinatorial branch-and-bound method for computing optimal bipartitionings of sparse matrices, in the sense that they have the lowest communication volume out of all possible bipartitionings obeying a certain load balance constraint. The method is based on a way of partitioning similar to the recently proposed medium-grain heuristic, which reduces the number of solutions to be considered in the branch-and-bound method. We applied the proposed optimal bipartitioner to find the optimal communication volume of all matrices of the University of Florida sparse matrix collection with 1000 nonzeros or less. For 85% of the matrices, an optimal bipartitioning was found within a single day of computation and for 58% even within a second. We also present optimal results for selected larger matrices, up to 129,042 nonzeros. The optimal bipartitionings and corresponding communication volumes are made publicly available in a benchmark collection. (C) 2015 Elsevier Inc. All rights reserved.

关键词： Branch-and-bound exact algorithm Hypergraph Parallel computing Partitioning Sparse matrix Sparse matrix-vector multiplication

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：