An official website of the United States government
We consider global optimization of nonconvex problems whose factorable reformulations contain a collection of multilinear equations. Important special cases include multilinear and polynomial optimization problems. The multilinear polytope is the convex hull of the set of binary points z satisfying the system of multilinear equations given above. Recently Del Pia and Khajavirad introduced running intersection inequalities, a family of facet-defining inequalities for the multilinear polytope. In this paper we address the separation problem for this class of inequalities. We first prove that separating flower inequalities, a subclass of running intersection inequalities, is NP-hard. Subsequently, for multilinear polytopes of fixed degree, we devise an efficient polynomial-time algorithm for separating running intersection inequalities and embed the proposed cutting-plane generation scheme at every node of the branch-and-reduce global solver BARON. To evaluate the effectiveness of the proposed method we consider two test sets: randomly generated multilinear and polynomial optimization problems of degree three and four, and computer vision instances from an image restoration problem Results show that running intersection cuts significantly improve the performance of BARON and lead to an average CPU time reduction of 50% for the random test set and of 63% for the image restoration test set.
more »
« less
Facets of Random Symmetric Edge Polytopes, Degree Sequences, and Clustering
Symmetric edge polytopes are lattice polytopes associated with finite simplegraphs that are of interest in both theory and applications. We investigate thefacet structure of symmetric edge polytopes for various models of randomgraphs. For an Erd\H{o}s-Renyi random graph, we identify a thresholdprobability at which with high probability the symmetric edge polytope sharesmany facet-supporting hyperplanes with that of a complete graph. We alsoinvestigate the relationship between the average local clustering, also knownas the Watts-Strogatz clustering coefficient, and the number of facets forgraphs with either a fixed number of edges or a fixed degree sequence. We usewell-known Markov Chain Monte Carlo sampling methods to generate empiricalevidence that for a fixed degree sequence, higher average local clustering in aconnected graph corresponds to higher facet numbers in the associated symmetricedge polytope.
more »
« less
- PAR ID:
- 10530877
- Publisher / Repository:
- arxiv
- Date Published:
- Journal Name:
- Discrete Mathematics & Theoretical Computer Science
- Volume:
- vol. 25:2
- Issue:
- Combinatorics
- ISSN:
- 1365-8050
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract The matching polytope of a graphGis the convex hull of the indicator vectors of the matchings onG. We characterize the graphs whose associated matching polytopes are Gorenstein, and then prove that all Gorenstein matching polytopes possess the integer decomposition property. As a special case study, we examine the matching polytopes of wheel graphs and show that they arenotGorenstein, butdopossess the integer decomposition property.more » « less
-
The separability of clusters is one of the most desired properties in clustering. There is a wide range of settings in which different clusterings of the same data set appear. We are interested in applications for which there is a need for an explicit, gradual transition of one separable clustering into another one. This transition should be a sequence of simple, natural steps that upholds separability of the clusters throughout. We design an algorithm for such a transition. We exploit the intimate connection of separability and linear programming over bounded-shape partition and transportation polytopes: separable clusterings lie on the boundary of partition polytopes and form a subset of the vertices of the corresponding transportation polytopes, and circuits of both polytopes are readily interpreted as sequential or cyclical exchanges of items between clusters. This allows for a natural approach to achieve the desired transition through a combination of two walks: an edge walk between two so-called radial clusterings in a transportation polytope, computed through an adaptation of classical tools of sensitivity analysis and parametric programming, and a walk from a separable clustering to a corresponding radial clustering, computed through a tailored, iterative routine updating cluster sizes and reoptimizing the cluster assignment of items. Funding: Borgwardt gratefully acknowledges support of this work through National Science Foundation [Grant 2006183] Circuit Walks in Optimization, Algorithmic Foundations, Division of Computing and Communication Foundations; through Air Force Office of Scientific Research [Grant FA9550-21-1-0233] The Hirsch Conjecture for Totally-Unimodular Polyhedra; and through Simons Collaboration [Grant 524210] Polyhedral Theory in Data Analytics. Happach has been supported by the Alexander von Humboldt Foundation with funds from the German Federal Ministry of Education and Research.more » « less
-
Ordering polytopes have been instrumental to the study of combinatorial optimization problems arising in a variety of fields including comparative probability, computational social choice, and group decision-making. The weak order polytope is defined as the convex hull of the characteristic vectors of all binary orders on n alternatives that are reflexive, transitive, and total. By and large, facet defining inequalities (FDIs) of this polytope have been obtained through simple enumeration and through connections with other combinatorial polytopes. This paper derives five new large classes of FDIs by utilizing the equivalent representations of a weak order as a ranking of n alternatives that allows ties; this connection simplifies the construction of valid inequalities, and it enables groupings of characteristic vectors into useful structures. We demonstrate that a number of FDIs previously obtained through enumeration are actually special cases of the large classes. This work also introduces novel construction procedures for generating affinely independent members of the identified ranking structures. Additionally, it states two conjectures on how to derive many more large classes of FDIs using the featured techniques.more » « less
-
Adjacency polytopes appear naturally in the study of nonlinear emergent phenomena in complex networks. The ``"PQ-type" adjacency polytope, denoted $$\nabla^{\mathrm{PQ}}_G$$ and which is the focus of this work, encodes rich combinatorial information about power-flow solutions in sparse power networks that are studied in electric engineering. Of particular importance is the normalized volume of such an adjacency polytope, which provides an upper bound on the number of distinct power-flow solutions. In this article we show that the problem of computing normalized volumes for $$\nabla^{\mathrm{PQ}}_G$$ can be rephrased as counting $D(G)$-draconian sequences where $D(G)$ is a certain bipartite graph associated to the network. We prove recurrences for all networks with connectivity at most $$1$$ and, for $$2$$-connected graphs under certain restrictions, we give recurrences for subdividing an edge and taking the join of an edge with a new vertex. Together, these recurrences imply a simple, non-recursive formula for the normalized volume of $$\nabla^{\mathrm{PQ}}_G$$ when $$G$$ is part of a large class of outerplanar graphs; we conjecture that the formula holds for all outerplanar graphs. Explicit formulas for several other (non-outerplanar) classes are given. Further, we identify several important classes of graphs $$G$$ which are planar but not outerplanar that are worth additional study.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.46298/dmtcs.9925
