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) li...
详细信息
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.
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 attenti...
详细信息
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.
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 polyt...
详细信息
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.
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 commun...
详细信息
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.
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 probl...
详细信息
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/).
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 ...
详细信息
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.
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 an...
详细信息
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.
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 ha...
详细信息
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.
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 a...
详细信息
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.
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 pre...
详细信息
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.
暂无评论