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

polyhedral combinatorics of UPGMA cones

ADVANCES IN APPLIED MATHEMATICS 2013年第2期50卷 327-338页

作者： Davidson, Ruth Sullivant, Seth N Carolina State Univ Dept Math Raleigh NC 27695 USA

Distance-based methods such as UPGMA (Unweighted Pair Group Method with Arithmetic Mean) continue to play a significant role in phylogenetic research. We use polyhedral combinatorics to analyze the natural subdivision of the positive orthant induced by classifying the input vectors according to tree topologies returned by the algorithm. The partition lattice informs the study of UPGMA trees. We give a closed form for the extreme rays of UPGMA cones on n taxa, and compute the spherical volumes of the UPGMA cones for small n. (c) 2012 Elsevier Inc. All rights reserved.

关键词： Phylogenetic trees polyhedral combinatorics Partition lattice

来源：评论

学校读者我要写书评

暂无评论

Information Theory and polyhedral combinatorics

Information Theory and Polyhedral Combinatorics

引用

Annual Allerton Conference on Communication, Control, and Computing

作者： Sebastian Pokutta the H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology Atlanta GA.

ISBN: (纸本)9781509018253

The theory of extended formulations is concerned with the optimal polyhedral representation of a (combinatorial) optimization problem. In this context, information-theoretic methods recently gained significant attention as a convenient way to provide strong lower bounds on the size of such representations. We will provide an introduction to information-theoretic methods in extended formulations, an overview of recent results, and discuss important open problems in extended formulations, which might be amenable to information-theoretic approaches.

关键词： Information Theory polyhedral combinatorics theory

来源：评论

学校读者我要写书评

暂无评论

Recycling valid inequalities for robust combinatorial optimization with budgeted uncertainty

引用

MATHEMATICAL PROGRAMMING 2025年第1-2期210卷 97-146页

作者： Buesing, Christina Gersing, Timo Koster, Arie M. C. A. Univ Klinikum RWTH Aachen Klin Unfall & Wiederherstellungsch D-52074 Aachen Germany Rhein Westfal TH Aachen Discrete Optimizat Pontdriesch 10-12 D-52062 Aachen Germany

Robust combinatorial optimization with budgeted uncertainty is one of the most popular approaches for integrating uncertainty into optimization problems. The existence of a compact reformulation for (mixed-integer) linear programs and positive complexity results give the impression that these problems are relatively easy to solve. However, the practical performance of the reformulation is quite poor when solving robust integer problems, in particular due to its weak linear relaxation. To overcome this issue, we propose procedures to derive new classes of valid inequalities for robust combinatorial optimization problems. For this, we recycle valid inequalities of the underlying deterministic problem such that the additional variables from the robust formulation are incorporated. The valid inequalities to be recycled may either be readily available model constraints or actual cutting planes, where we can benefit from decades of research on valid inequalities for classical optimization problems. We first demonstrate the strength of the inequalities theoretically, by proving that recycling yields a facet-defining inequality in many cases, even if the original valid inequality was not facet-defining. Afterwards, we show in an extensive computational study that using recycled inequalities can lead to a significant improvement of the computation time when solving robust optimization problems.

关键词： Robust optimization Combinatorial optimization Integer programming polyhedral combinatorics Computation

来源：评论

学校读者我要写书评

暂无评论

New facets of the clique partitioning polytope

引用

OPERATIONS RESEARCH LETTERS 2025年 59卷

作者： Letchford, Adam N. Sorensen, Michael M. Univ Lancaster Dept Management Sci Lancaster LA1 4YW England Aarhus Univ Dept Econ & Business Econ Fuglesangs Allee 4 DK-8210 Aarhus V Denmark

The clique partitioning problem is a combinatorial optimisation problem which has many applications. At present, the most promising exact algorithms are those that are based on an understanding of the associated polytope. We present two new families of valid inequalities for that polytope, and show that the inequalities define facets under certain conditions.

关键词： Clique partitioning problem Combinatorial optimisation polyhedral combinatorics

来源：评论

学校读者我要写书评

暂无评论

Optimizing over path-length matrices of unrooted binary trees

引用

MATHEMATICAL PROGRAMMING 2025年 1-53页

作者： Catanzaro, Daniele Pesenti, Raffaele Sapucaia, Allan Wolsey, Laurence Catholic Univ Louvain Ctr Operat Res & Econometr Voie Roman Pays 34 B-1348 Louvain la Neuve Belgium Univ CaFoscari Dept Management San GiobbeCannaregio 837 I-30121 Venice Italy

Path-Length Matrices (PLMs) form a tree encoding scheme that is often used in the context of optimization problems defined over Unrooted Binary Trees (UBTs). Determining the conditions that a symmetric integer matrix of order n >= 3 must satisfy to encode the PLM of a UBT with n leaves is central to these applications. Here, we show that a certain subset of known necessary conditions is also sufficient to characterize the set Theta(n) of PLMs induced by the set of UBTs with n leaves. We also identify key polyhedral results as well as facet-defining and valid inequalities for the convex hull of these matrices. We then examine how these results can be used to develop a new Branch- &-Cut algorithm for the Balanced Minimum Evolution Problem (BMEP), a NP-hard nonlinear optimization problem over Theta n much studied in the literature on molecular phylogenetics. We present a new valid integer linear programming formulation for this problem and we show how to refine it, by removing redundant variables and constraints. We also show how to strengthen the reduced formulation by including lifted versions of the previously identified facet-defining and valid inequalities. We provide separation oracles for these inequalities and we exploit the tight lower bound provided by the linear programming relaxation of this formulation to design a new primal heuristic for the BMEP. The results of extensive computational experiments show that the Branch- &-Cut algorithm derived from this study outperforms the current state-of-the-art exact solution algorithm for the problem.

关键词： Combinatorial optimization Integer programming polyhedral combinatorics Branch-& -cut Path-length matrices Unrooted binary trees Tree realization Kraft's equality Buneman's four-point conditions Balanced minimum evolution Distance methods Phylogenetics

来源：评论

学校读者我要写书评

暂无评论

SOLUTION OF LARGE-SCALE SYMMETRICAL TRAVELING SALESMAN PROBLEMS

引用

MATHEMATICAL PROGRAMMING 1991年第2期51卷 141-202页

作者： GROTSCHEL, M HOLLAND, O UNIV BONN INST OPERAT RESFORSCHUNGSINST DISKRETE MATHW-5300 BONNGERMANY

In this paper we report on a cutting plane procedure with which we solved symmetric travelling salesman problems of up to 1000 cities to optimality. Our implementation is based on a fast LP-solver (IBM's MPSX) and makes effective use of polyhedral results on the symmetric travelling salesman polytope. We describe the important ingredients of our code and give an extensive documentation of its computational performance.

关键词： TRAVELING SALESMAN PROBLEM CUTTING PLANE ALGORITHMS polyhedral combinatorics

来源：评论

学校读者我要写书评

暂无评论

Facets of the polytope of the Asymmetric Travelling Salesman Problem with Replenishment Arcs

引用

DISCRETE OPTIMIZATION 2006年第1期3卷 33-49页

作者： Mak, Vicky Boland, Natashia Deakin Univ Sch Informat Technol Burwood Vic 3125 Australia Univ Melbourne Dept Math & Stat Melbourne Vic 3010 Australia

The Asymmetric Travelling Salesman Problem with Replenishment Arcs (RATSP) is a new class of problems arising from work related to aircraft routing. Given a digraph with cost on the arcs, a solution of the RATSP, like that of the Asymmetric Travelling Salesman Problem, induces a directed tour in the graph which minimises total cost. However the tour must satisfy additional constraints: the arc set is partitioned into replenishment arcs and ordinary arcs, each node has a non-negative weight associated with it, and the tour cannot accumulate more than some weight limit before a replenishment arc must be used. To enforce this requirement, constraints are needed. We refer to these as replenishment constraints. In this paper, we review previous polyhedral results for the RATSP and related problems, then prove that two classes of constraints developed in V. Mak and N. Boland [polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs, Technical Report TR M05/03, School of Information Technology, Deakin University, 2005] are, under appropriate conditions, facet-defining for the RATS polytope. (c) 2005 Elsevier B.V. All rights reserved.

关键词： combinatorial optimisation travelling salesman polyhedral combinatorics

来源：评论

学校读者我要写书评

暂无评论

The biclique partitioning polytope

引用

DISCRETE APPLIED MATHEMATICS 2021年 301卷 118-130页

作者： de Sousa Filho, Gilberto F. Bulhoes, Teobaldo Cabral, Lucidio dos Anjos F. Ochi, Luiz Satoru Protti, Fabio Pinheiro, Rian G. S. Univ Fed Paraiba UFPB Ctr Informat Dept Comp Cient Joao Pessoa Paraiba Brazil Univ Fed Fluminense UFF Inst Comp Niteroi RJ Brazil Univ Fed Alagoas UFAL Inst Comp Maceio Alagoas Brazil

Given a bipartite graph G = (V-1, V-2, E), a biclique of G is a complete bipartite subgraph of G, and a biclique partitioning of G is a set A subset of E such that the bipartite graph G' = (V-1, V-2, A) is a vertex-disjoint union of bicliques. The biclique partitioning problem (BPP) consists of, given a complete bipartite graph G = (V-1, V-2, E) with edge weights w(e) is an element of R for all e is an element of E (thus, negative weights are allowed), finding a biclique partitioning A subset of E of minimum weight. The bicluster editing problem (BEP) is a variant of the BPP and consists of editing a minimum number of edges of an input bipartite graph G in order to transform its edge set into a biclique partitioning. Editing an edge consists of either adding it to the graph or deleting it from the graph. In addition to the BPP and the BEP, other problems in the literature aim at finding biclique partitionings, and this motivates the study of the biclique partitioning polytope P-nm of the complete bipartite graph K-nm (i.e., P-nm is the convex hull of the incidence vectors of the biclique partitionings of K-nm). In this paper we develop such a polyhedral study and show that ladder, bellows, and grid inequalities induce facets of P-nm. Our computational results show that these inequalities are very effective in solving the BEP. In particular, they are able to improve the value of the relaxed solution by up to 20%. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Biclique partitioning polyhedral combinatorics Facet-inducing inequalities

来源：评论

学校读者我要写书评

暂无评论

polyhedral RESULTS FOR 1-RESTRICTED SIMPLE 2-MATCHINGS

引用

SIAM JOURNAL ON OPTIMIZATION 2008年第3期19卷 1131-1149页

作者： Hartvigsen, David Li, Yanjun Univ Notre Dame Mendoza Coll Business Notre Dame IN 46556 USA Purdue Univ Krannert Sch Management W Lafayette IN 47907 USA

A simple 2-matching in a graph is a subgraph whose connected components are nontrivial paths and cycles. A simple 2-matching is called 1-restricted if each connected component has two or more edges. In this paper we consider the problem of finding maximum weight 1-restricted simple 2-matchings (which is a relaxation of the traveling salesman problem). We present an integer programming formulation for this problem, characterize the extreme points of the linear programming relaxation, and characterize the graphs for which the linear programming relaxation has all integral extreme points. We show how to recognize these graphs in polynomial time. We also introduce a new class of blossom-type inequalities that tighten the general linear programming relaxation. A complete description of the convex hull of 1-restricted simple 2-matchings is unknown.

关键词： matchings combinatorial optimization polyhedral combinatorics traveling salesman problem

来源：评论

学校读者我要写书评

暂无评论

The capacitated arc routing problem: Valid inequalities and facets

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 1998年第2期10卷 165-187页

作者： Belenguer, JM Benavent, E Univ Valencia Dept Estadist & Invest Operat E-46100 Valencia Spain

In this paper we study the polyhedron associated with the Capacitated Arc Routing Problem (CARP) where a maximum number K of vehicles is available. We show that a subset of the facets of the CARP polyhedron depends only on the demands of the required edges and they can be derived from the study of the Generalized Assignment Problem (GAP). The conditions for a larger class of valid inequalities to define facets of the CARP polyhedron still depend on the properties of the GAP polyhedron. We introduce the special case of the CARP where all the required edges have unit demand (CARPUD) to avoid the number problem represented by the GAP. This allows us to make a polyhedral study in which the conditions for the inequalities to be facet inducing are easily verifiable. We give necessary and sufficient conditions for a variety of inequalities, which are valid for CARP, to be facet inducing for CARPUD. The resulting partial description of the polyhedron has been used to develop a cutting plane algorithm for the Capacitated Arc Routing Problem. The lower bound provided by this algorithm outperformed all the existing lower bounds for the CARP on a set of 34 instances taken from the literature.

关键词： routing arc routing problems integer programming polyhedral combinatorics

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：