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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Cuts and semidefinite liftings for the complex cut polytope

引用

MATHEMATICAL PROGRAMMING 2024年 1-50页

作者： Sinjorgo, Lennart Sotirov, Renata Anjos, Miguel F. Tilburg Univ Dept Econometr & OR Tilburg Netherlands Univ Edinburgh Sch Math Edinburgh Scotland

We consider the complex cut polytope: the convex hull of Hermitian rank 1 matrices xx(H), where the elements of x is an element of C-n aremth unit roots. These polytopes have appli-cations in MAX-3-CUT, digital communication technology, angular synchronizationand more generally, complex quadratic programming. Form=2, the complex cutpolytope corresponds to the well-known cut polytope. We generalize valid cuts for this polytope to cuts for any complex cut poly tope with finitem>2 and provide a frame work to compare them. Further, we consider a second semi definite lifting of thecomplex cut polytope for m=infinity. This lifting is proven to be equivalent to other complex Lasserre-type liftings of the same order proposed in the literature, while beingof smaller size. Our theoretical findings are supported by numerical experiments onvarious optimization problems.

关键词： Complex semidefinite programming Complex cut polytope polyhedral combinatorics MIMO Angular synchronization

来源：评论

学校读者我要写书评

暂无评论

polyhedral approach to weighted connected matchings in general graphs

引用

DISCRETE APPLIED MATHEMATICS 2024年 359卷 143-152页

作者： Samer, Phillippe Moura, Phablo F. S. Univ Bergen Inst Informatikk Postboks 7800 N-5020 Bergen Norway Katholieke Univ Leuven Res Ctr Operat Res & Stat Leuven Belgium

A connected matching in a graph G consists of a set of pairwise disjoint edges whose covered vertices induce a connected subgraph of G . While finding a connected matching of maximum cardinality is a well-solved problem, it is NP-hard to determine an optimal connected matching in an edge-weighted graph, even in the planar bipartite case. We present two mixed integer programming formulations and a sophisticated branch-and- cut scheme to find weighted connected matchings in general graphs. The formulations explore different polyhedra associated to this problem, including strong valid inequalities both from the matching polytope and from the connected subgraph polytope. We conjecture that one attains a tight approximation of the convex hull of connected matchings using our strongest formulation, and report encouraging computational results over DIMACS Implementation Challenge benchmark instances. The source code of the complete implementation is also made available. (c) 2024 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).

关键词： Connected matchings Combinatorial optimization polyhedral combinatorics Integer programming Induced connectivity Connected subgraphs

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Integer programming models and polyhedral study for the geodesic classification problem on graphs

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2024年第3期314卷 894-911页

作者： Araujo, Paulo H. M. Campelo, Manoel Correa, Ricardo C. Labbe, Martine Univ Fed Ceara Quixada Brazil Univ Fed Ceara Fortaleza Brazil Univ Fed Rural Rio de Janeiro Nova Iguacu Brazil Free Univ Brussels Brussels Belgium

We study a discrete version of the classical classification problem in Euclidean space, to be called the geodesic classification problem. It is defined on a graph, where some vertices are initially assigned a class and the remaining ones must be classified. This vertex partition into classes is grounded on the concept of geodesic convexity on graphs, as a replacement for Euclidean convexity in the multidimensional space. We propose two new integer programming models along with branch-and-bound algorithms to solve them. We also carry out a polyhedral study of the associated polyhedra, which produced families of facetdefining inequalities and separation algorithms. Finally, we run computational experiments to evaluate the computational efficiency and the classification accuracy of the proposed approaches by comparing them with classic solution methods for the Euclidean convexity classification problem. (c) 2023 Elsevier B.V. All rights reserved.

关键词： Combinatorial optimization Classification Geodesic convexity polyhedral combinatorics Integer programming

来源：评论

学校读者我要写书评

暂无评论

Rigidity of Nonconvex Polyhedra with Respect to Edge Lengths and Dihedral Angles

引用

DISCRETE & COMPUTATIONAL GEOMETRY 2024年 1-35页

作者： Cho, Yunhi Kim, Seonhwa Univ Seoul Dept Math Seoul 02504 South Korea Korea Inst Adv Study Seoul 02455 South Korea

We prove that every three-dimensional polyhedron is uniquely determined by its dihedral angles and edge lengths, even if nonconvex or self-intersecting, under two plausible sufficient conditions: (i) the polyhedron has only convex faces and (ii) it does not have partially-flat vertices, and under an additional technical requirement that (iii) any triple of vertices is not collinear. The proof is consistently valid for Euclidean, hyperbolic and spherical geometry, which takes a completely different approach from the argument of the Cauchy rigidity theorem. Various counterexamples are provided that arise when these conditions are violated, and self-contained proofs are presented whenever possible. As a corollary, the rigidity of several families of polyhedra is also established. Finally, we propose two conjectures: the first suggests that Condition (iii) can be removed, and the second concerns the rigidity of spherical nonconvex polygons.

关键词： Rigidity polyhedral combinatorics Nonconvex polyhedra Spherical polygons

来源：评论

学校读者我要写书评

暂无评论

Multilinear sets with two monomials and cardinality constraints

引用

DISCRETE APPLIED MATHEMATICS 2023年 324卷 67-79页

作者： Chen, Rui Dash, Sanjeeb Gunluk, Oktay Cornell Tech New York NY 10044 USA IBM Res Armonk NY USA Cornell Univ Ithaca NY 14853 USA

Binary polynomial optimization is equivalent to the problem of minimizing a linear function over the intersection of the multilinear set with a polyhedron. Many families of valid inequalities for the multilinear set are available in the literature, though giving a polyhedral characterization of the convex hull is not tractable in general as binary polynomial optimization is NP-hard. In this paper, we study the cardinality constrained multilinear set in the special case when the number of monomials is exactly two. We give an extended formulation, with two more auxiliary variables and exponentially many inequalities, of the convex hull of solutions of the standard linearization of this problem. We also show that the separation problem can be solved efficiently. (c) 2022 Elsevier B.V. All rights reserved.

关键词： Binary polynomial optimization Cardinality constraint polyhedral combinatorics

来源：评论

学校读者我要写书评

暂无评论

Formulations and valid inequalities for the capacitated dispersion problem

引用

NETWORKS 2023年第2期81卷 294-315页

作者： Landete, Mercedes Peiro, Juanjo Yaman, Hande Univ Miguel Hernandez Elche Inst Ctr Invest Operat Dept Estadist Matemat & Informat Elche Spain Univ Valencia Fac Ciencies Matemat Dept Estadist & Invest Operat Valencia Spain Katholieke Univ Leuven Res Ctr Operat Res & Business Stat ORSTAT Fac Econ & Business Leuven Belgium

This work focuses on the capacitated dispersion problem for which we study several mathematical formulations in different spaces using variables associated with nodes, edges, and costs. The relationships among the presented formulations are investigated by comparing the projections of the feasible sets of the LP relaxations onto the subspace of natural variables. These formulations are then strengthened with families of valid inequalities and variable-fixing procedures. The separation problems associated with the valid inequalities that are exponential in number are shown to be polynomially solvable by reducing them to longest path problems in acyclic graphs. The dual bounds obtained from stronger but larger formulations are used to improve the strength of weaker but smaller formulations. Several sets of computational experiments are conducted to illustrate the usefulness of the findings, as well as the aptness of the formulations for different types of instances.

关键词： dispersion problem extended formulation location science polyhedral combinatorics separation telescopic sums valid inequalities

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：