-
作者：Ostrowski, James; Anjos, Miguel F.; Vannelli, Anthony
作者单位：University of Tennessee System; University of Tennessee Knoxville; Universite de Montreal; Universite de Montreal; Polytechnique Montreal; University of Guelph
摘要：The past decade has seen advances in general methods for symmetry breaking in mixed-integer linear programming. These methods are advantageous for general problems with general symmetry groups. Some important classes of mixed integer linear programming problems, such as bin packing and graph coloring, contain highly structured symmetry groups. This observation has motivated the development of problem-specific techniques. In this paper we show how to strengthen orbital branching in order to exp...
-
作者：Cornuejols, Gerard; Schaefer, Andrew
作者单位：Carnegie Mellon University; Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh
-
作者：Kummer, Mario; Plaumann, Daniel; Vinzant, Cynthia
作者单位：University of Konstanz; University of Michigan System; University of Michigan
摘要：Hyperbolic polynomials are real polynomials whose real hypersurfaces are maximally nested ovaloids, the innermost of which is convex. These polynomials appear in many areas of mathematics, including optimization, combinatorics and differential equations. Here we investigate the special connection between a hyperbolic polynomial and the set of polynomials that interlace it. This set of interlacers is a convex cone, which we write as a linear slice of the cone of nonnegative polynomials. In part...
-
作者：Briet, Jop; Dadush, Daniel; Pokutta, Sebastian
作者单位：New York University; University System of Georgia; Georgia Institute of Technology
摘要：In Rothvo (Math Program 142(1-2):255-268, 2013) it was shown that there exists a 0/1 polytope (a polytope whose vertices are in ) such that any higher-dimensional polytope projecting to it must have facets, i.e., its linear extension complexity is exponential. The question whether there exists a 0/1 polytope with high positive semidefinite extension complexity was left open. We answer this question in the affirmative by showing that there is a 0/1 polytope such that any spectrahedron projectin...
-
作者：Shitov, Yaroslav
作者单位：HSE University (National Research University Higher School of Economics)
摘要：The tropical arithmetic operations on , defined as and , arise from studying the geometry over non-Archimedean fields. We present an application of tropical methods to the study of extended formulations for convex polytopes. We propose a non-Archimedean generalization of the well known Boolean rank bound for the extension complexity. We show how to construct a real polytope with the same extension complexity and combinatorial type as a given non-Archimedean polytope. Our results allow us to de...
-
作者：Pilanci, Mert; Wainwright, Martin J.; El Ghaoui, Laurent
作者单位：University of California System; University of California Berkeley; University of California System; University of California Berkeley
摘要：We introduce novel relaxations for cardinality-constrained learning problems, including least-squares regression as a special but important case. Our approach is based on reformulating a cardinality-constrained problem exactly as a Boolean program, to which standard convex relaxations such as the Lasserre and Sherali-Adams hierarchies can be applied. We analyze the first-order relaxation in detail, deriving necessary and sufficient conditions for exactness in a unified manner. In the special c...
-
作者：Mahjoub, A. Ridha; Rinaldi, Giovanni; Woeginger, Gerhard
作者单位：Universite PSL; Universite Paris-Dauphine; Consiglio Nazionale delle Ricerche (CNR); Istituto di Analisi dei Sistemi ed Informatica Antonio Ruberti (IASI-CNR); Eindhoven University of Technology
-
作者：Fawzi, Hamza; Parrilo, Pablo A.
作者单位：Massachusetts Institute of Technology (MIT)
摘要：The nonnegative rank of an entrywise nonnegative matrix is the smallest integer such that can be written as where and are both nonnegative. The nonnegative rank arises in different areas such as combinatorial optimization and communication complexity. Computing this quantity is NP-hard in general and it is thus important to find efficient bounding techniques especially in the context of the aforementioned applications. In this paper we propose a new lower bound on the nonnegative rank which, u...
-
作者：Kaibel, Volker; Thomas, Rekha
作者单位：Otto von Guericke University; University of Washington; University of Washington Seattle
-
作者：Faenza, Yuri; Fiorini, Samuel; Grappe, Roland; Tiwary, Hans Raj
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Universite Libre de Bruxelles; Centre National de la Recherche Scientifique (CNRS); Universite Paris 13; Charles University Prague
摘要：An extended formulation of a polyhedron is a linear description of a polyhedron together with a linear map such that . These objects are of fundamental importance in polyhedral combinatorics and optimization theory, and the subject of a number of studies. Yannakakis' factorization theorem (Yannakakis in J Comput Syst Sci 43(3):441-466, 1991) provides a surprising connection between extended formulations and communication complexity, showing that the smallest size of an extended formulation of ...
