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

A separation algorithm FOR THE MATCHABLE SET POLYTOPE

MATHEMATICAL PROGRAMMING 1994年第2期65卷 139-150页

作者： CUNNINGHAM, WH GREENKROTKI, J UNIV WATERLOO DEPT COMBINATOR & OPTIMIZAT WATERLOO N2L 3G1 ONTARIO CANADA UNIV BONN FORSCHUNGSINST DISKRETE MATH W-5300 BONN GERMANY

A matchable set of a graph is a set of vertices joined in pairs by disjoint edges. Balas and Pulleyblank gave a linear-inequality description of the convex hull of matchable sets. We give a polynomial-time conbinatorial algorithm for the separation problem for this polytope, and a min-max theorem characterizing the maximum violation by a given point of an inequality of the system.

关键词： COMBINATORIAL OPTIMIZATION POLYHEDRA MATCHING MATCHABLE SET separation algorithm AUGMENTING PATH

来源：评论

学校读者我要写书评

暂无评论

separation algorithm for Tree Partitioning Inequalities

引用

Electronic Notes in Discrete Mathematics 2016年 52卷 109-116页

作者： Chopra, Sunil Lee, Kangbok Ryu, Minseok Shim, Sangho J.L. Kellogg Graduate School of Management Northwestern University Evanston 60208 IL United States Department of Business and Economics York College The City University of New York Jamaica 11451 NY United States Department of Industrial and Operations Engineering University of Michigan Ann Arbor 48109 MI United States Department of Engineering Robert Morris University Moon Twp 15108 PA United States

We consider the tree partition problem to partition the node set of a tree into subsets where the induced subgraph by each subset is connected and the total weight of nodes in a subset cannot exceed the capacity of the subset. We identify exponentially many valid inequalities for an integer programming formulation of the problem and develop a linear time separation algorithm for the valid inequalities. © 2016 Elsevier B.V.

关键词： Integer programming separation algorithm Tree partitioning Valid inequality

来源：评论

学校读者我要写书评

暂无评论

New separation algorithm for touching grain kernels based on contour segments and ellipse fitting

引用

Journal of Zhejiang University-Science C(Computers and Electronics) 2011年第1期12卷 54-61页

作者： Lei YAN Cheol-Woo PARK Sang-Ryong LEE Choon-Young LEE School of Mechanical Engineering Kyungpook National University Daegu 702-701 Korea School of Technology Beijing Forestry University Beijing 100083 China

A new separation algorithm based on contour segments and ellipse fitting is proposed to separate the ellipse-like touching grain kernels in digital *** image is filtered and converted into a binary image *** the contour of touching grain kernels is extracted and divided into contour segments (CS) with the concave points on *** next step is to merge the contour segments,which is the main contribution of this *** distance measurement (DM) and deviation error measurement (DEM) are proposed to test whether the contour segments pertain to the same kernel or *** they pass the measurement and judgment,they are merged as a new *** with these newly merged contour segments,the ellipses are fitted as the representative ellipses for touching *** verify the proposed algorithm,six different kinds of Korean grains were *** results showed that the proposed method is efficient and accurate for the separation of the touching grain kernels.

关键词： separation algorithm Touching grains Contour segments Ellipse fitting

来源：评论

学校读者我要写书评

暂无评论

A separation algorithm for Improved LP-Decoding of Linear Block Codes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2010年第7期56卷 3277-3289页

作者： Tanatmis, Akin Ruzika, Stefan Hamacher, Horst W. Punekar, Mayur Kienle, Frank Wehn, Norbert Univ Kaiserslautern Dept Math D-67663 Kaiserslautern Germany Univ Kaiserslautern Microelect Syst Design Res Grp D-67663 Kaiserslautern Germany

Maximum likelihood (ML) decoding is the optimal decoding algorithm for arbitrary linear block codes and can be written as an integer programming (IP) problem. Feldman et al. relaxed this IP problem and presented linear programming (LP) based decoding. In this paper, we propose a new separation algorithm to improve the error-correcting performance of LP decoding for binary linear block codes. We use an IP formulation with indicator variables that help in detecting the violated parity checks. We derive Gomory cuts from the IP and use them in our separation algorithm. An efficient method of finding cuts induced by redundant parity checks (RPC) is also proposed. Under certain circumstances we can guarantee that these RPC cuts are valid and cut off the fractional optimal solutions of LP decoding. It is demonstrated on three LDPC codes and two BCH codes that our separation algorithm performs significantly better than LP decoding and belief propagation (BP) decoding.

关键词： Integer programming (IP) linear programming (LP) decoding maximum likelihood (ML) decoding separation algorithm

来源：评论

学校读者我要写书评

暂无评论

A cut-and-branch algorithm for the external candidates examination scheduling problem

引用

JOURNAL OF SCHEDULING 2025年 1-8页

作者： Avella, Pasquale Boccia, Maurizio Mannino, Carlo Mele, Michele Viglione, Sandro Univ Sannio Dipartimento Ingn Benevento Italy Univ Naples Federico II Dept Elect Engn & Informat Technol Naples Italy SINTEF Digital Oslo Norway Univ Oslo Oslo Norway

Twice a year, the regional school departments in Norway need to schedule examination sessions for external candidates in the region, which also involves reserving and assigning rooms, examiners and reviewers. We present a cut-and-branch algorithm to get provably good solutions to this problem, the external candidates examination scheduling problem (ExtSchedule). The algorithm relies on a new family of valid inequalities, effective in tightening the initial formulation and accelerating the solution process. We develop an efficient separation algorithm and embed it in a cut-and-branch framework to solve the problem. The algorithm has been validated on real-life instances arising from the Vestfold County school department in Norway.

关键词： Valid inequalities Cut-and-branch separation algorithm Scheduling

来源：评论

学校读者我要写书评

暂无评论

Valid Inequalities and separation algorithms for the Set Partitioning Problem

引用

INFOR 2014年第4期52卷 185-196页

作者： Groiez, Mounira Desaulniers, Guy Marcotte, Odile Ecole Polytech Gerad Montreal PQ H3C 3A7 Canada Ecole Polytech Dept Math & Genie Ind Montreal PQ H3C 3A7 Canada Univ Quebec Gerad Montreal PQ H3C 3P8 Canada Univ Quebec Dept Informat Montreal PQ H3C 3P8 Canada

In this article we investigate some strategies for solving set partitioning problems (SPP), in particular the gains in computational efficiency that can be obtained by introducing cutting planes based on some rank-1 Chvatal-Gomory inequalities and clique inequalities. We show that for many instances of the SPP, the introduction of some of these cutting planes into the standard SPP model enables a commercial solver such as CPLEX to compute optimal solutions more efficiently.

关键词： set partitioning cutting planes rank-1 Chvatal-Gomory inequalities clique separation algorithm

来源：评论

学校读者我要写书评

暂无评论

Exact separation algorithms for the Parallel Drone Scheduling Traveling Salesman Problem 12th

Exact Separation Algorithms for the Parallel Drone Schedulin...

引用

12th International Conference on Computational Logistics (ICCL)

作者： Klein, Tobias Becker, Peter Univ Appl Sci Hsch Bonn Rhein Sieg H BRS St Augustin Germany

ISBN: (纸本)9783030876722;9783030876715

The joint delivery of parcels by trucks and drones is a futuristic scenario that already started. As a result of this development, new optimization problems are defined and studied. In this paper, exact separation algorithms for the Parallel Drone Scheduling Traveling Salesman Problem are presented. Known separation algorithms for subtour elimination constraints and 2-matching inequalities are modified and applied to the new context. In addition, a new valid inequality for an invalid drone-truck subtour is given. For this inequality, a simple separation algorithm with a runtime of O(n(2)) for n nodes (customers) is presented. It is shown that this problem specific separation algorithm reduces the total runtime of problem instances more effectively compared to modified TSP approaches, especially for instances with a large number of customers that can be served by a drone. These separation algorithms are used to solve instances with up to 127 customers by a branch and cut algorithm.

关键词： Parallel drone scheduling traveling salesman problem PDSTSP Integer programming Branch and cut separation algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient underdetermined speech signal separation using encompassed Hammersley- Clifford algorithm and hardware implementation

引用

MICROPROCESSORS AND MICROSYSTEMS 2021年 85卷 104300-104300页

作者： Velammal, Navaneetha M. Kumar, Nirmal P. Francis Xavier Engn Coll Dept Elect & Commun Engn Tirunelveli India Anna Univ Coll Engn Dept Elect & Commun Engn Chennai Tamil Nadu India

Speech separation is among the propelled advances for a wide range of uses in different sectors, where detachment from the Blind Source separation Signal is a troublesome task. Blind source separation is a growing digital signal processing industry to separate the precise signal from the recorded dense. Exclusively, among the "Blind Source separation," the "Under Determined Blind Source separation" is considered as an Over Determined Blind Source separation due to its wide range of usage. Nevertheless, it is seen that real implementation is very rarely done in existing researches because the real-time Implementation of UBSS (Underdetermined Blind Source separation) exists to be a challenging one due to its lacking hardware characteristics of increased latency, reduced speed and consumption of more memory space. Consequently, an increasing need to implement an Underdetermined source signal separation in real-time with improved hardware utility. In this Unswerving framework, a Real-time feasible Source Signal separator formulated in which the source signals decomposed by Boosted Band-Limited VMD (Variational Mode Decomposition) "Multicomponent Signal". The amount of "BandLimited" Intrinsic Mode Function (BLIMF) was subjected to the Encompassed Hammersley-Clifford algorithm for source separation using Expectation-Maximization and Gibbs Sampling, an alternative to deterministic algorithms and to determine the exact estimated parameter from the E-M method. Subsequently, the source separation algorithm infers the best separation of source signals by exact estimation and determination from the decomposed signals. The iterations in E-M estimation reduced by the Gauss-Seidel Method. Thus, our novel source signal separates internally with a signal decomposer and a source separation algorithm with fewer iterations, which reduces memory consumption and yields better hardware realization with reduced latency and increased speed. The proposed implementation is done by utilizing M

关键词： Boosted band-limited VMD separation algorithm Gauss-Seidel method Encompassed Hammersley-Clifford source separation algorithm

来源：评论

学校读者我要写书评

暂无评论

Lifting and separation procedures for the cut polytope

引用

MATHEMATICAL PROGRAMMING 2014年第1-2期146卷 351-378页

作者： Bonato, Thorsten Juenger, Michael Reinelt, Gerhard Rinaldi, Giovanni Heidelberg Univ Inst Informat Heidelberg Germany Univ Cologne Inst Informat D-50931 Cologne Germany CNR Ist Anal Sistemi & Informat A Ruberti Rome Italy

The max-cut problem and the associated cut polytope on complete graphs have been extensively studied over the last 25 years. However, in comparison, only little research has been conducted for the cut polytope on arbitrary graphs, in particular separation algorithms have received only little attention. In this study we describe new separation and lifting procedures for the cut polytope on general graphs. These procedures exploit algorithmic and structural results known for the cut polytope on complete graphs to generate valid, and sometimes facet defining, inequalities for the cut polytope on arbitrary graphs in a cutting plane framework. We report computational results on a set of well-established benchmark problems.

关键词： Max-cut problem Cut polytope separation algorithm Branch-and-cut Unconstrained boolean quadratic programming Ising spin glass model

来源：评论

学校读者我要写书评

暂无评论

Faster separation of 1-wheel inequalities by graph products

引用

DISCRETE APPLIED MATHEMATICS 2015年 195卷 74-83页

作者： de Vries, Sven Univ Trier FB Math 4 D-54286 Trier Germany

Using graph products we present an O(vertical bar V vertical bar E-2 vertical bar vertical bar + vertical bar V vertical bar(3) log vertical bar V vertical bar) separation algorithm for the nonsimple 1-wheel inequalities by Cheng and Cunningham (1997) of the stable set polytope, which is faster than their O(vertical bar V vertical bar(4)) algorithm. There are two ingredients for our algorithm. The main improvement stems from a reduction of the separation problem to multiple shortest path problems in an auxiliary graph having only 6 vertical bar V vertical bar vertices and 9 vertical bar E vertical bar arcs, thereby preserving low sparsity. Then Johnson's algorithm can be applied to the auxiliary graph of same sparsity as the original one. In contrast, Cheng and Cunningham's auxiliary graph is by construction dense, vertical bar E vertical bar = O((vertical bar V vertical bar(2))), so application of Johnson's algorithm provides no large improvement. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Graph product Stable set separation algorithm Wheel

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：