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

A polyhedral study of the maximum edge subgraph problem

DISCRETE APPLIED MATHEMATICS 2012年第18期160卷 2573-2590页

作者： Bonomo, Flavia Marenco, Javier Saban, Daniela Stier-Moses, Nicolas E. Univ Buenos Aires FCEyN Dept Comp RA-1053 Buenos Aires DF Argentina IMAS CONICET Buenos Aires DF Argentina Univ Nacl Gen Sarmiento Inst Ciencias Buenos Aires DF Argentina Columbia Univ Grad Sch Business New York NY 10027 USA

The study of cohesive subgroups is an important aspect of social network analysis. Cohesive subgroups are studied using different relaxations of the notion of clique in a graph. For instance, given a graph and an integer k, the maximum edge subgraph problem consists of finding a k-vertex subset such that the number of edges within the subset is maximum. This work proposes a polyhedral approach for this NP-hard problem. We study the polytope associated to an integer programming formulation of the problem, present several families of facet-inducing valid inequalities, and discuss the separation problem associated to these families. Finally, we implement a branch and cut algorithm for this problem. This computational study illustrates the effectiveness of the classes of inequalities presented in this work. (C) 2011 Elsevier B.V. All rights reserved.

关键词： polyhedral combinatorics Quasi-cliques Maximum edge subgraph problem

来源：评论

学校读者我要写书评

暂无评论

Generalised 2-circulant inequalities for the max-cut problem

引用

OPERATIONS RESEARCH LETTERS 2022年第2期50卷 122-128页

作者： Kaparis, Konstantinos Letchford, Adam N. Mourtos, Ioannis Univ Macedonia Dept Business Adm QMeDA Lab Thessaloniki Greece Univ Lancaster Dept Management Sci Lancaster England Athens Univ Econ & Business Dept Management Sci & Technol ELTRUN Res Lab Athens Greece

The max cut problem is a fundamental combinatorial optimisation problem, with many applications. Poljak and Turzik found some facet-defining inequalities for the associated polytope, which we call 2-circulant inequalities. We present a more general family of facet-defining inequalities, an exact separation algorithm that runs in polynomial time, and some computational results. (C) 2022 Elsevier B.V. All rights reserved.

关键词： Max-cut problem polyhedral combinatorics Cutting planes

来源：评论

学校读者我要写书评

暂无评论

Stable multi-sets

引用

MATHEMATICAL METHODS OF OPERATIONS RESEARCH 2002年第1期56卷 45-65页

作者： Koster, AMCA Zymolka, A Konrad Zuse Zentrum Informat Tech Berlin D-14195 Berlin Germany

In this paper we introduce a generalization of stable sets: stable multisets. A stable multi-set is an assignment of integers to the vertices of a graph, such that specified bounds on vertices and edges are not exceeded. In case all vertex and edge bounds equal one, stable multi-sets are equivalent to stable sets. For the stable multi-set problem, we derive reduction rules and study the associated polytope. We state necessary and sufficient conditions for the extreme points of the linear relaxation to be integer. These conditions generalize the conditions for the stable set polytope. Moreover, the classes of odd cycle and clique inequalities for stable sets are generalized to stable multi-sets and conditions for them to be facet defining are determined. The study of stable multi-sets is initiated by optimization problems in the field of telecommunication networks. Stable multi-sets emerge as an important substructure in the design of optical networks.

关键词： generalized stable sets polyhedral combinatorics valid inequalities

来源：评论

学校读者我要写书评

暂无评论

ON DYADIC FRACTIONAL PACKINGS OF T-JOINS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2022年第3期36卷 2445-2451页

作者： Abdit, Ahmad Cornuejols, Gerard Palion, Zuzanna London Sch Econ & Polit Sci Math London WC2A 2AE England Carnegie Mellon Univ Tepper Sch Business Pittsburgh PA 15213 USA BlackRock London EC2N 2DL England

Let G = (V, E) be a graph, and T subset of V a nonempty subset of even cardinality. The famous theorem of Edmonds and Johnson on the T-join polyhedron implies that the minimum cardinality of a T-cut is equal to the maximum value of a fractional packing of T-joins. In this paper, we prove that the fractions assigned may be picked as dyadic rationals, i.e., of the form a/2(k) for some integers a, k >= 0.

关键词： T-joins integral polyhedron dyadic rational T-cuts polyhedral combinatorics combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

ON NONCONVEX QUADRATIC PROGRAMMING WITH BOX CONSTRAINTS

引用

SIAM JOURNAL ON OPTIMIZATION 2009年第2期20卷 1073-1089页

作者： Burer, Samuel Letchford, Adam N. Univ Iowa Dept Management Sci Tippie Coll Business Iowa City IA 52242 USA Univ Lancaster Dept Management Sci Lancaster LA1 4YX England

Nonconvex quadratic programming with box constraints is a fundamental NP-hard global optimization problem. Recently, some authors have studied a certain family of convex sets associated with this problem. We prove several fundamental results concerned with these convex sets: we determine their dimension, characterize their extreme points and vertices, show their invariance under certain a. ne transformations, and show that various linear inequalities induce facets. We also show that the sets are closely related to the Boolean quadric polytope, a fundamental polytope in the field of polyhedral combinatorics. Finally, we give a classification of valid inequalities and show that this yields a finite recursive procedure to check the validity of any proposed inequality.

关键词： nonconvex quadratic programming global optimization polyhedral combinatorics convex analysis

来源：评论

学校读者我要写书评

暂无评论

The mixing-MIR set with divisible capacities

引用

MATHEMATICAL PROGRAMMING 2008年第1期115卷 73-103页

作者： Zhao, M. de Farias, I. R., Jr. Univ Buffalo Dept Ind & Syst Engn Buffalo NY 14260 USA SUNY New York NY USA

We study the set = {(x, y) is an element of R+ x Z(n) : x + B(j)y(j) >= b(j), j=1,..., n}, where B-j, b(j) is an element of R+ -{0}, j = 1,..., n, and B-1 vertical bar...vertical bar B-n. The set S generalizes the mixed-integer rounding (MIR) set of Nemhauser and Wolsey and the mixing-MIR set of Gunluk and Pochet. In addition, it arises as a substructure in general mixed-integer programming (MIP), such as in lot-sizing. Despite its importance, a number of basic questions about S remain unanswered, including the tractability of optimization over S and how to efficiently find a most violated cutting plane valid for P = conv (S). We address these questions by analyzing the extreme points and extreme rays of P. We give all extreme points and extreme rays of P. In the worst case, the number of extreme points grows exponentially with n. However, we show that, in some interesting cases, it is bounded by a polynomial of n. In such cases, it is possible to derive strong cutting planes for P efficiently. Finally, we use our results on the extreme points of P to give a polynomial-time algorithm for solving optimization over S.

关键词： mixed-integer programming branch-and-cut polyhedral combinatorics simple-set cutting plane simple mixed-integer set lot-sizing computational complexity

来源：评论

学校读者我要写书评

暂无评论

On the combinatorics of the 2-class classification problem

引用

DISCRETE OPTIMIZATION 2019年 31卷 40-55页

作者： Correa, Ricardo C. Delle Donne, Diego Marenco, Javier Univ Fed Rural Rio de Janeiro Dept Ciencia Comp Av Governador Roberto Silveira S-N BR-26020740 Nova Iguacu RJ Brazil Univ Nacl Gen Sarmiento Inst Ciencias JM Gutierrez 1150 RA-1613 Buenos Aires DF Argentina

A set of points X = X-B boolean OR X-R subset of R-d is linearly separable if the convex hulls of X-B and X-R are disjoint, hence there exists a hyperplane separating X-B from X-R. Such a hyperplane provides a method for classifying new points, according to which side of the hyperplane the new points lie. When such a linear separation is not possible, it may still be possible to partition X-B and X-R into prespecified numbers of groups, in such a way that every group from X-B is linearly separable from every group from X-R. We may also discard some points as outliers, and seek to minimize the number of outliers necessary to find such a partition. Based on these ideas, Bertsimas and Shioda proposed the classification and regression by integer optimization (CRIO) method in 2007. In this work we explore the integer programming aspects of the classification part of CRIO, in particular theoretical properties of the associated formulation. We are able to find facet-inducing inequalities coming from the stable set polytope, hence showing that this classification problem has exploitable combinatorial properties. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Classification Integer programming polyhedral combinatorics

来源：评论

学校读者我要写书评

暂无评论

Optimizing constrained subtrees of trees

引用

MATHEMATICAL PROGRAMMING 1995年第2期71卷 113-126页

作者： Aghezzaf, EH Magnanti, TL Wolsey, LA FAC UNIV CATHOLIQUE MONSBELGIUM MIT ALFRED P SLOAN SCH MANAGEMENTCAMBRIDGEMA 02139 MIT SCH ENGNCAMBRIDGEMA 02139 UNIV CATHOLIQUE LOUVAIN COREB-1348 LOUVAINBELGIUM

Given a tree G = (V, E) and a weight function defined on subsets of its nodes, we consider two associated problems. The first, called the ''rooted subtree problem'', is to find a maximum weight subtree, with a specified root, from a given set of subtrees. The second problem, called ''the subtree packing problem'', is to find a maximum weight packing of node disjoint subtrees chosen from a given set of subtrees, where the value of each subtree may depend on its root. We show that the complexity status of both problems is related, and that the subtree packing problem is polynomial if and only if each rooted subtree problem is polynomial, In addition we show that the convex hulls of the feasible solutions to both problems are related: the convex hull of solutions to the packing problem is given by ''pasting together'' the convex hulls of the rooted subtree problems. We examine in detail the case where the set of feasible subtrees rooted at node i consists of all subtrees with at most k nodes, For this case we derive valid inequalities, and specify the convex hull when k less than or equal to 4.

关键词： polyhedral combinatorics packing subtrees knapsacks with precedence column generation dynamic programming

来源：评论

学校读者我要写书评

暂无评论

The traveling salesman problem on cubic and subcubic graphs

引用

MATHEMATICAL PROGRAMMING 2014年第1-2期144卷 227-245页

作者： Boyd, Sylvia Sitters, Ren van der Ster, Suzanne Stougie, Leen Univ Ottawa Sch Elect Engn & Comp Sci Ottawa ON Canada Vrije Univ Amsterdam Dept Operat Res Amsterdam Netherlands CWI NL-1009 AB Amsterdam Netherlands

We study the traveling salesman problem (TSP) on the metric completion of cubic and subcubic graphs, which is known to be NP-hard. The problem is of interest because of its relation to the famous 4/3-conjecture for metric TSP, which says that the integrality gap, i.e., the worst case ratio between the optimal value of a TSP instance and that of its linear programming relaxation (the subtour elimination relaxation), is 4/3. We present the first algorithm for cubic graphs with approximation ratio 4/3. The proof uses polyhedral techniques in a surprising way, which is of independent interest. In fact we prove constructively that for any cubic graph on vertices a tour of length exists, which also implies the 4/3-conjecture, as an upper bound, for this class of graph-TSP. Recently, Momke and Svensson presented an algorithm that gives a 1.461-approximation for graph-TSP on general graphs and as a side result a 4/3-approximation algorithm for this problem on subcubic graphs, also settling the 4/3-conjecture for this class of graph-TSP. The algorithm by Momke and Svensson is initially randomized but the authors remark that derandomization is trivial. We will present a different way to derandomize their algorithm which leads to a faster running time. All of the latter also works for multigraphs.

关键词： Traveling salesman problem Approximation algorithms Subtour elimination Matching polytope polyhedral combinatorics

来源：评论

学校读者我要写书评

暂无评论

The QAP-polytope and the graph isomorphism problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2018年第3期36卷 965-1006页

作者： Aurora, Pawan Mehta, Shashank K. IISER Bhopal Bhopal India IIT Kanpur Kanpur Uttar Pradesh India

In this paper we propose a geometric approach to solve the Graph Isomorphism (GI in short) problem. Given two graphs G1, G2, the GI problem is to decide if the given graphs are isomorphic i. e., there exists an edge preserving bijection between the vertices of the two graphs. We propose an Integer Linear Program (ILP) that has a non-empty solution if and only if the given graphs are isomorphic. The convex hull of all possible solutions of the ILP has been studied in literature as the Quadratic Assignment Problem (QAP) polytope. We study the feasible region of the linear programming relaxation of the ILP and show that the given graphs are isomorphic if and only if this region intersects with the QAP-polytope. As a consequence, if the graphs are not isomorphic, the feasible region must lie entirely outside the QAP-polytope. We study the facial structure of the QAP-polytope with the intention of using the facet defining inequalities to eliminate the feasible region outside the polytope. We determine two new families of facet defining inequalities of the QAP-polytope and show that all the known facet defining inequalities are special instances of a general inequality. Further we define a partial ordering on each exponential sized family of facet defining inequalities and show that if there exists a common minimal violated inequality for all points in the feasible region outside the QAP-polytope, then we can solve the GI problem in polynomial time. We also study the general case when there are k such inequalities and give an algorithm for the GI problem that runs in time exponential in k.

关键词： Quadratic assignment problem Graph isomorphism problem polyhedral combinatorics

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：