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

Partitioning a graph into balanced connected classes: Formulations, separation and experiments

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2021年第3期293卷 826-836页

作者： Miyazawa, Flavio K. Moura, Phablo F. S. Ota, Matheus J. Wakabayashi, Yoshiko Univ Estadual Campinas Inst Comp Campinas Brazil Univ Fed Minas Gerais Dept Ciencia Comp Belo Horizonte MG Brazil Univ Sao Paulo Inst Matemat & Estat Sao Paulo Brazil

This work addresses the balanced connected k-partition problem (BCPk), which is formally defined as follows. Given a connected graph G = (V, E) with nonnegative weights on the vertices, find a partition {V-i}(i=1)(k) of V such that each class V-i induces a connected subgraph of G, and the weight of a class with the minimum weight is as large as possible. This problem, known to be NP-hard, has been largely investigated under different approaches and perspectives: exact algorithms, approximation algorithms for some values of k or special classes of graphs, and inapproximability results. On the practical side, BCPk is used to model many applications arising in image processing, cluster analysis, operating systems and robotics. We propose three linear programming formulations for BCPk. The first one contains only binary variables and a potentially large number of constraints that can be separated in polynomial time in the corresponding linear relaxation. We introduce new valid inequalities and design polynomial-time separation algorithms for them. The other two formulations are based on flows and have a polynomial number of constraints and variables. Our computational experiments show that the exact algorithms based on the proposed formulations outperform the other exact approaches presented in the literature. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Integer programming Branch-and-cut separation algorithm Balanced partition Connected partition

来源：评论

学校读者我要写书评

暂无评论

separation routine and extended formulations for the stable set problem in claw-free graphs

引用

MATHEMATICAL PROGRAMMING 2021年第1期188卷 53-84页

作者： Faenza, Yuri Oriolo, Gianpaolo Stauffer, Gautier Columbia Univ IEOR Dept New York NY USA Univ Tor Vergata Dipartimento Ingn Civile & Ingn Informat Rome Italy KEDGE Business Sch Ctr Excellence Supply Chain Innovat & Transportat Talence France

The maximum weighted stable set problem in claw-free graphs is a well-known generalization of the maximum weighted matching problem, and a classical problem in combinatorial optimization. In spite of the recent development of fast(er) combinatorial algorithms and some progresses in the characterization of the corresponding stable set polytope, the problem of "providing a decent linear description" for this polytope (Grotschel et al. in Geometric algorithms and combinatorial optimization, Springer, New York, 1988) is still open. The main contribution of this paper is to propose an algorithmic answer to that question by providing a polynomial-time and computationally attractive separation routine for the stable set polytope of claw-free graphs, that only requires a combinatorial decomposition algorithm, the solution of (moderate sized) compact linear programs, and Padberg and Rao's algorithm for separating over the matching polytope. In particular, it is a generalization of the latter and avoids the heavy computational burden of resorting to the ellipsoid method, on which the only poly-time separation routine known so far relied. Besides, our separation routine comes with a 'small' (but not polynomial) extended linear programming formulation and a procedure to derive a linear description of the stable set polytope of claw-free graphs in the original space.

关键词： Claw-free graphs Stable set polytope separation algorithm Extended formulations

来源：评论

学校读者我要写书评

暂无评论

separation of dynamic data and recovery of P-abnormal data

引用

INTERNATIONAL JOURNAL OF MACHINE LEARNING AND CYBERNETICS 2017年第4期8卷 1119-1129页

作者： Li, Yuying Li, Jintong Ruan, Qunsheng Wu, Yuqin Ningde Normal Univ Dept Comp Ningde 352100 Peoples R China Ningde Normal Univ Dept Lib Ningde 352100 Peoples R China

The main purpose of this paper is to study abnormal data whose data elements are increased and decreased simultaneously in data transmission. By using a new mathematic model of P-sets which has dynamic characteristics, this paper proposes the concepts of -abnormal data, -abnormal data, -abnormal data and P-abnormal data, including -lost data and -intrusive data. P-abnormal data consists of -abnormal data, -abnormal data and -abnormal data. Based on research for P-abnormal data, the paper also gives a separation algorithm for dynamic data by using P-sets and the set difference operation on general set. By using this algorithm, information systems can determine whether the detected data is standard. If the data is not standard, it can be separated into -abnormal data or -abnormal data. In addition, this paper gives a method for recognition of P-abnormal data and two methods for recovery of P-abnormal data. Finally, this paper provides an application for the separation of dynamic data and recovery of P-abnormal data. The study shows that the separation algorithm is a new mathematical tool. It can be applied in data processing which has the internal dynamic characteristics, outer dynamic characteristics or both dynamic characteristics simultaneously.

关键词： P sets P abnormal data Set difference operation separation algorithm Data recovery

来源：评论

学校读者我要写书评

暂无评论

separation of partition inequalities for the (1,2)-survivable network design problem

引用

OPERATIONS RESEARCH LETTERS 2002年第4期30卷 265-268页

作者： Kerivin, H Mahjoub, AR Univ Clermont Ferrand Lab LIMOS CNRS F-63177 Clermont Ferrand France

Given a graph G = (V, E) with edge costs and an integer vector r is an element of Z(+)(V) associated with network design problem is to find a minimum cost subgraph of G such that between every pair of nodes s, t of V, there are at least min{r(s), r(t)} edge-disjoint paths. In this paper we consider that problem when r is an element of {1, 2}(V). This case is of particular interest to the telecommunication industry. We show that the separation problem for the so-called partition inequalities reduces to minimizing a submodular function. This yields a polynomial time separation algorithm for these inequalities in that case. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： survivable network partition inequalities submodular function separation algorithm

来源：评论

学校读者我要写书评

暂无评论

Optimization of separation on the basis of UNIFAC parameters and evaluation of the composition of the stationary phase in gas-liquid chromatography

引用

CHROMATOGRAPHIA 2003年第11-12期57卷 831-833页

作者： Mukhamadiev, NQ Sayitkulov, SM Ergashev, IM Khafizov, KF Fayzullaev, NI Samarkand State Univ Dept Chem Samarkand 703004 Uzbekistan

An algorithm for the optimisation of separation in gas-liquid chromatography based on varying the composition of the stationary phase and the column temperature is presented using the critical parameter R-S greater than or equal to 0.75 (SigmaR(S) double right arrow max). The stationary phase composition, on the basis of retention parameters expressed in terms of vapour pressure and activity coefficient has been derived. Determination of the composition of the stationary liquid was carried out by defining the nature of solute-solvent interactions using group additive value contributions to the activity coefficients. Predicting values on experimentally determined parameters reduced calculation errors by a factor 2 to 3. The results of the analysis of liquid products from the synthesis of vinyl chloride and chloroprene from acetylene and HCl are presented. The results reveal the mechanism of the reaction and allow optimum conditions to be obtained.

关键词： gas chromatography separation algorithm UNIFAC parameters stationary phase composition acetylene, vinyl chloride and chloroprene

来源：评论

学校读者我要写书评

暂无评论

separation of Multiple Partial Discharge Sources in Power Transformer

Separation of Multiple Partial Discharge Sources in Power Tr...

引用

International Conference on High Voltage Engineering and Power Systems (ICHVEPS)

作者： Zhang, Guan-Jun Wang, Yan-Bo Chang, Ding-Ge Shao, Xian-Jun Zhan, Jiang-Yang He, Wen-Lin Xi An Jiao Tong Univ Sch Elect Engn State Key Lab Elect Insulat & Power Equipment Xian 710049 Shaanxi Peoples R China State Grid Zhejiang Elect Power Res Inst Hangzhou 310014 Zhejiang Peoples R China

ISBN: (纸本)9781538609453

Partial discharge (PD) in power transformer degrades the dielectric insulation and results in insulation failure and breakdown after a long period. In fact, a partial discharge detector can gather signals from two or more PD sources which increase the difficulty on pattern recognition and insulation state assessment. How to separate multiple PD signals is meaningful to subsequent data processing. In this paper, a PD separation algorithm based on cumulative energy (CE) function is introduced. The CE functions in time domain (TCE) and frequency domain (FCE) are calculated from PD waveforms and their FFT spectra, respectively. By using an oblique line to cross the CE curves, width features are extracted from the intersection points between them. Through the mathematical morphology gradient (MMG) operation, sharpness features are extracted to characterize the rise steepness of CE. A clustering algorithm is adopted to discover different clusters in feature space and separate PD signals. After that, a transformer experiment platform is introduced and some different defects are placed at different places in this transformer to produce PD signals. The pulse current method is applied to gather their PD waveforms and to record phase resolved partial discharge (PRPD) which can be used to analyse discharge characteristics of different defects. The separation algorithm is examined with mixed PD current pulses acquired from experiments. The results prove the feasibility of separation algorithm with different PD defects.

关键词： Multiple partial discharge separation algorithm power transformers cumulative energy function

来源：评论

学校读者我要写书评

暂无评论

THE MULTILINEAR POLYTOPE FOR ACYCLIC HYPERGRAPHS

引用

SIAM JOURNAL ON OPTIMIZATION 2018年第2期28卷 1049-1076页

作者： Del Pia, Alberto Khajavirad, Aida Univ Wisconsin Dept Ind & Syst Engn Madison WI 53706 USA Univ Wisconsin Wisconsin Inst Discovery Madison WI 53706 USA Carnegie Mellon Univ Dept Chem Engn Pittsburgh PA 15213 USA

We consider the multilinear polytope defined as the convex hull of the set of binary points z satisfying a collection of equations of the form z(e) = Pi(zv)(v is an element of e), e is an element of E, where E denotes a family of subsets of {1, . . . , n} of cardinality at least two. Such sets are of fundamental importance in many types of mixed-integer nonlinear optimization problems, such as 0 - 1 polynomial optimization. Utilizing an equivalent hypergraph representation, we study the facial structure of the multilinear polytope in conjunction with the acyclicity degree of the underlying hypergraph. We provide explicit characterizations of the multilinear polytopes corresponding to Berge-acylic and gamma-acyclic hypergraphs. As the multilinear polytope for gamma-acyclic hypergraphs may contain exponentially many facets in general, we present a strongly polynomial-time algorithm to solve the separation problem, implying polynomial solvability of the corresponding class of 0 - 1 polynomial optimization problems. As an important byproduct, we present a new class of cutting planes for constructing tighter polyhedral relaxations of mixed-integer nonlinear optimization problems with multilinear subexpressions.

关键词： multilinear polytope cutting planes hypergraph acyclicity separation algorithm mixed-integer nonlinear optimization

来源：评论

学校读者我要写书评

暂无评论

Modeling and solving the mixed capacitated general routing problem

引用

OPTIMIZATION LETTERS 2013年第7期7卷 1451-1469页

作者： Bosco, Adamo Lagana, Demetrio Musmanno, Roberto Vocaturo, Francesca Univ Calabria Dipartimento Elettron Informat & Sistemist I-87036 Arcavacata Di Rende CS Italy Univ Calabria Dipartimento Econ & Stat I-87036 Arcavacata Di Rende CS Italy

We tackle the mixed capacitated general routing problem (MCGRP) which generalizes many other routing problems. We propose an integer programming model for the MCGRP and extend some inequalities originally introduced for the capacitated arc routing problem (CARP). Identification procedures for these inequalities and for some relaxed constraints are also discussed. Finally, we describe a branch and cut algorithm including the identification procedures and present computational experiments over instances derived from the CARP.

关键词： Routing problem Mixed graph Relaxation separation algorithm

来源：评论

学校读者我要写书评

暂无评论

Facets of the axial three-index assignment polytope

引用

DISCRETE APPLIED MATHEMATICS 2016年 201卷 86-104页

作者： Dokka, Trivikram Spieksma, Frits C. R. Univ Lancaster Sch Management Dept Management Sci Lancaster LA1 4YW England Katholieke Univ Leuven ORSTAT Naamsestr 69 B-3000 Louvain Belgium

We revisit the facial structure of the axial 3-index assignment polytope. After reviewing known classes of facet-defining inequalities, we present a new class of valid inequalities, and show that they define facets of this polytope. This answers a question posed by Qi and Sun (2000). Moreover, we show that we can separate these inequalities in polynomial time. Finally, we assess the computational relevance of the new inequalities by performing (limited) computational experiments. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Three-dimensional assignment Polyhedral methods Facets separation algorithm

来源：评论

学校读者我要写书评

暂无评论

A Branch and Cut solver for the maximum stable set problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2011年第4期21卷 434-457页

作者： Rebennack, Steffen Oswald, Marcus Theis, Dirk Oliver Seitz, Hanna Reinelt, Gerhard Pardalos, Panos M. Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA Univ Heidelberg Discrete Optimizat Res Grp Heidelberg Germany Univ Magdeburg Fak Math IMO D-39106 Magdeburg Germany

This paper deals with the cutting-plane approach to the maximum stable set problem. We provide theoretical results regarding the facet-defining property of inequalities obtained by a known project-and-lift-style separation method called edge-projection, and its variants. An implementation of a Branch and Cut algorithm is described, which uses edge-projection and two other separation tools which have been discussed for other problems: local cuts (pioneered by Applegate, Bixby, Chvatal and Cook) and mod-k cuts. We compare the performance of this approach to another one by Rossi and Smiriglio (Oper. Res. Lett. 28:63-74, 2001) and discuss the value of the tools we have tested.

关键词： Maximum stable set problem Cutting-plane algorithm Branch and Cut separation algorithm Edge-projection

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：