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

On the exact solution of the no-wait flow shop problem with due date constraints

COMPUTERS & OPERATIONS RESEARCH 2017年第May期81卷 141-159页

作者： Samarghandi, Hamed Behroozi, Mehdi Univ Saskatchewan Edwards Sch Business Dept Finance & Management Sci Saskatoon SK S7N 5A7 Canada Northeastern Univ Dept Mech & Ind Engn 334 Snell Engn Ctr360 Huntington Ave Boston MA 02115 USA

This paper deals with the no-wait flow shop scheduling problem with due date constraints. In the no wait flow shop problem, waiting time is not allowed between successive operations of jobs. Moreover, the jobs should be completed before their respective due dates;due date constraints are dealt with as hard constraints. The considered performance criterion is makespan. The problem is strongly NP-hard. This paper develops a number of distinct mathematical models for the problem based on different decision variables. Namely, a mixed integer programming model, two quadratic mixed integer programming models, and two constraint programming models are developed. Moreover, a novel graph representation is developed for the problem. This new modeling technique facilitates the investigation of some of the important characteristics of the problem;this results in a number of propositions to rule out a large number of infeasible solutions from the set of all possible permutations. Afterward, the new graph representation and the resulting propositions are incorporated into a new exact algorithm to solve the problem to optimality. To investigate the performance of the mathematical models and to compare them with the developed exact algorithm, a number of test problems are solved and the results are reported. Computational results demonstrate that the developed algorithm is significantly faster than the mathematical models. (C) 2016 Elsevier Ltd. All rights reserved.

关键词： No-wait flow shop Due date constraints Mixed integer programming Constraint programming enumeration algorithm

来源：评论

学校读者我要写书评

暂无评论

Computational determination of the largest lattice polytope diameter

引用

DISCRETE APPLIED MATHEMATICS 2020年 281卷 106-110页

作者： Chadder, Nathan Deza, Antoine McMaster Univ Dept Comp & Software Adv Optimizat Lab Hamilton ON Canada

A lattice (d, k)-polytope is the convex hull of a set of points in dimension d whose coordinates are integers between 0 and k. Let delta(d, k) be the largest diameter over all lattice (d, k)-polytopes. We develop a computational framework to determine delta(d, k) for small instances. We show that delta(3, 4) = 7 and delta(3, 5) = 9;that is, we verify for (d, k) = (3, 4) and (3, 5) the conjecture whereby delta(d, k) is at mostleft perpendicular (k + 1)d/2right perpendicular and is achieved, up to translation, by a Minkowski sum of lattice vectors. (c) 2019 Elsevier B.V. All rights reserved.

关键词： Lattice polytope Edge-graph diameter enumeration algorithm

来源：评论

学校读者我要写书评

暂无评论

Complex Korkine-Zolotareff Reduction algorithm for Full-Diversity MIMO Detection

引用

IEEE COMMUNICATIONS LETTERS 2013年第2期17卷 381-384页

作者： Jiang, Hua Du, Sidan Nanjing Univ Sch Elect Sci & Engn Nanjing 210093 Jiangsu Peoples R China

The Korkine-Zolotareff (KZ) reduced basis is considered as the best reduced basis for use in data decoding in multiple-input multiple-output (MIMO) communication systems. In this paper, we present an improved KZ algorithm for direct application in reducing a complex lattice basis. The enumeration algorithm, which is the dominant contributor to the main cost of the KZ algorithm, is also modified for a complex lattice. We reduce the number of iterations in the KZ algorithm to reduce complexity without degrading performance. In addition, we show that KZ-reduction-aided decoding is capable of achieving full diversity. Simulation results demonstrate the excellent performance and low complexity of the improved algorithm.

关键词： Korkine-Zolotareff reduction lattice reduction multiple-input multiple-output (MIMO) enumeration algorithm full diversity

来源：评论

学校读者我要写书评

暂无评论

A branch and bound algorithm for designing reliable systems at a minimum cost

引用

APPLIED MATHEMATICS AND COMPUTATION 2001年第2-3期118卷 247-259页

作者： Djerdjour, M Rekab, K SUNY Coll Plattsburgh Sch Business & Econ Plattsburgh NY 12901 USA Florida Inst Technol Dept Math Sci Melbourne FL 32901 USA

A nonlinear integer programming model for the optimal design of a series/parallel reliability system is presented, together with an enumeration algorithm for its solution and an example. The algorithm is based on an efficient procedure for solving the continuous relaxation of the mathematical model. (C) 2001 Elsevier Science Inc. All rights reserved.

关键词： nonlinear integer programming reliability mathematical model enumeration algorithm

来源：评论

学校读者我要写书评

暂无评论

On 1324-avoiding permutations

引用

ADVANCES IN APPLIED MATHEMATICS 2015年第1期64卷 50-69页

作者： Conway, Andrew R. Guttmann, Anthony J. Univ Melbourne Dept Math & Stat ARC Ctr Excellence Math & Stat Complex Syst Melbourne Vic 3010 Australia

We give an improved algorithm for counting the number of 1324-avoiding permutations, resulting in 5 further terms of the generating function. We analyse the known coefficients and find compelling evidence that unlike other classical length-4 pattern-avoiding permutations, the generating function in this case does not have an algebraic singularity. Rather, the number of 1324-avoiding permutations of length n behaves as ***(n).mu(n sigma)(1).n(g). We estimate mu= 11.60 +/- 0.01, sigma = 1/2, mu(1) = 0.040 +/- 0.0015, g= -1.1 +/- 0.2 and B = 7 +/- 1.3. (C) 2014 Elsevier Inc. All rights reserved.

关键词： Permutation patterns enumeration algorithm Asymptotics

来源：评论

学校读者我要写书评

暂无评论

Mining maximal cliques from a large graph using MapReduce: Tackling highly uneven subproblem sizes

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2015年 79-80卷 104-114页

作者： Svendsen, Michael Mukherjee, Arko Provo Tirthapura, Srikanta Iowa State Univ Dept Elect & Comp Engn Ames IA 50011 USA

We consider Maximal Clique enumeration (MCE) from a large graph. A maximal clique is perhaps the most fundamental dense substructure in a graph, and MCE is an important tool to discover densely connected subgraphs, with numerous applications to data mining on web graphs, social networks, and biological networks. While effective sequential methods for MCE are known, scalable parallel methods for MCE are still lacking. We present a new parallel algorithm for MCE, Parallel enumeration of Cliques using Ordering (PECO), designed for the MapReduce framework. Unlike previous works, which required a post-processing step to remove duplicate and non-maximal cliques, PECO enumerates only maximal cliques with no duplicates. The key technical ingredient is a total ordering of the vertices of the graph which is used in a novel way to achieve a load balanced distribution of work, and to eliminate redundant work among processors. We implemented PECO on Hadoop MapReduce, and our experiments on a cluster show that the algorithm can effectively process a variety of large real-world graphs with millions of vertices and tens of millions of maximal cliques, and scales well with the degree of available parallelism. (C) 2014 Elsevier Inc. All rights reserved.

关键词： Graph mining Maximal clique enumeration enumeration algorithm MapReduce Hadoop Parallel algorithm Clique Load balancing

来源：评论

学校读者我要写书评

暂无评论

Linear-time algorithm for generating c-isolated bicliques

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2017年第8期94卷 1574-1590页

作者： Alamgir, Zareen Karim, Saira Husnine, Syed Natl Univ Comp & Emerging Sci Dept Comp Sci Block B Lahore Pakistan Natl Univ Comp & Emerging Sci Dept Math Lahore Pakistan

Bicliques are widely used to solve various real-world problems encountered in bio-informatics, data mining and networks. We consider c-isolated bicliques, a variation of bicliques. The c-isolated bicliques can model communities in social and biological networks. We propose an efficient algorithm to generate all c-isolated maximal bicliques in a given bipartite graph. Our algorithm exploits underlying properties of an isolated biclique to trim the input graph. Furthermore, the algorithm deploys the vertex cover enumeration algorithm based on fixed parameter tractability and lists all maximal c-isolated bicliques in linear time (in terms of graph size), for constant c.

关键词： Combinatorial algorithm enumeration algorithm biclique isolated biclique graph algorithms 68R10 68Q25 90C35 05C69

来源：评论

学校读者我要写书评

暂无评论

Efficiently enumerating hitting sets of hypergraphs arising in data profiling

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2022年 124卷 192-213页

作者： Blaesius, Thomas Friedrich, Tobias Lischeid, Julius Meeks, Kitty Schirneck, Martin Karlsruhe Inst Technol Karlsruhe Germany Univ Potsdam Hasso Plattner Inst Potsdam Germany Univ Glasgow Glasgow Lanark Scotland

The transversal hypergraph problem asks to enumerate the minimal hitting sets of a hypergraph. If the solutions have bounded size, Eiter and Gottlob [SICOMP'95] gave an algorithm running in output-polynomial time, but whose space requirement also scales with the output. We improve this to polynomial delay and space. Central to our approach is the extension problem, deciding for a set X of vertices whether it is contained in any minimal hitting set. We show that this is one of the first natural problems to be W[3]-complete. We give an algorithm for the extension problem running in time O(m(vertical bar X vertical bar+1) n) and prove a SETH-lower bound showing that this is close to optimal. We apply our enumeration method to the discovery problem of minimal unique column combinations from data profiling. Our empirical evaluation suggests that the algorithm outperforms its worst-case guarantees on hypergraphs stemming from real-world databases. (C) 2021 Elsevier Inc. All rights reserved.

关键词： Data profiling enumeration algorithm Minimal hitting set Transversal hypergraph Unique column combination W[3]-Completeness

来源：评论

学校读者我要写书评

暂无评论

Exact and heuristic algorithms for the domination problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2024年第3期313卷 926-936页

作者： Inza, Ernesto Parra Vakhania, Nodari Almira, Jose Maria Sigarreta Mira, Frank Angel Hernandez UAEMor Ctr Invest Ciencias Cuernavaca Morelos Mexico Univ Autonoma Guerrero Fac Matemat Acapulco De Juarez Guerrero Mexico UAGro Ctr Ciencias Desarrollo Reg Acapulco De Juarez Guerrero Mexico

In a simple connected graph G = (V, E) , a subset of vertices S subset of V is a dominating set if any vertex v is an element of V \ S is adjacent to some vertex x from this subset. A number of real-life problems can be modeled using this problem which is known to be among the difficult NP-hard problems in its class. We formulate the problem as an integer liner program (ILP) and compare the performance with the two earlier existing exact state-of-the-art algorithms and exact implicit enumeration and heuristic algorithms that we propose here. Our exact algorithm was able to find optimal solutions much faster than ILP and the above two exact algorithms for middle-dense instances. For graphs with a considerable size, our heuristic algorithm was much faster than both, ILP and our exact algorithm. It found an optimal solution for more than half of the tested instances, whereas it improved the earlier known state-of-the-art solutions for almost all the tested benchmark instances. Among the instances where the optimum was not found, it gave an average approximation error of 1.18.

关键词： Graph theory Dominating set enumeration algorithm Heuristic Time complexity Combination optimization

来源：评论

学校读者我要写书评

暂无评论

Routing Optimization of Fourth Party Logistics with Reliability Constraints based on Messy GA

引用

JOURNAL OF INDUSTRIAL ENGINEERING AND MANAGEMENT-JIEM 2014年第5期7卷 1097-1111页

作者： Li Jia Liu Yanqiu Hu Zhongjun Shenyang Univ Technol China Sch Management Shenyang Peoples R China

Purpose: The purpose of this paper is to choose a optimal routing in fourth party logistics (4PL) with the objective of transportation cost minimization under reliability level constraint. Design/methodology/approach: Reliability theory is applied to routing optimization problem. A mathematical model of the 4PL routing optimization problem with reliability constraints is built, which aims to find a route at the minimum cost. Due to the 4PL routing problem is NP-hard, two algorithms are designed: Messy Genetic algorithm (Messy GA) and enumeration algorithm ( EA). Findings: Through the model and algorithm, 4PL company can obtain the optimal solution quickly and effectively, according to customer's reliability requirements. Practical implications: We give an example for test the effectiveness of the method and the algorithm. Originality/value: In this paper, we put objective factors that cause disturbances of transportation time into consideration, and reliability theory is applied to 4PL routing optimization problem. A Messy GA with double arrays encoding method is designed to solve the problem.

关键词： fourth party logistics routing optimization reliability constraints Messy Genetic algorithm enumeration algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：