-
作者：Goemans, Michel X.
作者单位：Massachusetts Institute of Technology (MIT)
摘要：In this note, we consider the permutahedron, the convex hull of all permutations of . We show how to obtain an extended formulation for this polytope from any sorting network. By using the optimal Ajtai-Komls-Szemer,di sorting network, this extended formulation has variables and inequalities. Furthermore, from basic polyhedral arguments, we show that this is best possible (up to a multiplicative constant) since any extended formulation has at least inequalities. The results easily extend to th...
-
作者：Leovey, H.; Roemisch, W.
作者单位：Humboldt University of Berlin
摘要：Quasi-Monte Carlo (QMC) algorithms are studied for generating scenarios to solve two-stage linear stochastic programming problems. Their integrands are piecewise linear-quadratic, but do not belong to the function spaces considered for QMC error analysis. We show that under some weak geometric condition on the two-stage model all terms of their ANOVA decomposition, except the one of highest order, are continuously differentiable and second order mixed derivatives exist almost everywhere and be...
-
作者：Pang, C. H. Jeffrey
作者单位：National University of Singapore
摘要：We study how the supporting hyperplanes produced by the projection process can complement the method of alternating projections and its variants for the convex set intersection problem. For the problem of finding the closest point in the intersection of closed convex sets, we propose an algorithm that, like Dykstra's algorithm, converges strongly in a Hilbert space. Moreover, this algorithm converges in finitely many iterations when the closed convex sets are cones in satisfying an alignment c...
-
作者：An, Hyung-Chan; Bhaskara, Aditya; Chekuri, Chandra; Gupta, Shalmoli; Madan, Vivek; Svensson, Ola
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Alphabet Inc.; Google Incorporated; University of Illinois System; University of Illinois Urbana-Champaign
摘要：We consider the capacitated -center problem. In this problem we are given a finite set of locations in a metric space and each location has an associated non-negative integer capacity. The goal is to choose (open) locations (called centers) and assign each location to an open center to minimize the maximum, over all locations, of the distance of the location to its assigned center. The number of locations assigned to a center cannot exceed the center's capacity. The uncapacitated -center probl...
-
作者：Kaibel, Volker; Walter, Matthias
作者单位：Otto von Guericke University
摘要：We introduce the simple extension complexity of a polytope as the smallest number of facets of any simple (i.e., non-degenerate in the sense of linear programming) polytope which can be projected onto . We devise a combinatorial method to establish lower bounds on the simple extension complexity and show for several polytopes that they have large simple extension complexities. These examples include both the spanning tree and the perfect matching polytopes of complete graphs, uncapacitated flo...
-
作者：Korupolu, Madhukar; Meyerson, Adam; Rajaraman, Rajmohan; Tagiku, Brian
作者单位：Alphabet Inc.; Google Incorporated; Northeastern University
摘要：In modern data centers and cloud computing systems, jobs often require resources distributed across nodes providing a wide variety of services. Motivated by this, we study the Coupled Placement problem, in which we place jobs into computation and storage nodes with capacity constraints, so as to optimize some costs or profits associated with the placement. The coupled placement problem is a natural generalization of the widely-studied generalized assignment problem, which concerns the placemen...
-
作者：Conforti, Michele; Gerards, Bert; Pashkovich, Kanstantsin
作者单位：University of Padua; University of Waterloo
摘要：We develop decomposition/composition tools for efficiently solving maximum weight stable sets problems as well as for describing them as polynomially sized linear programs (using compact systems). Some of these are well-known but need some extra work to yield polynomial decomposition schemes. We apply the tools to graphs with no even hole and no cap. A hole is a chordless cycle of length greater than three and a cap is a hole together with an additional node that is adjacent to two adjacent no...
-
作者：Fiorini, Samuel; Pashkovich, Kanstantsin
作者单位：Universite Libre de Bruxelles; University of Padua
摘要：An extended formulation of a polytope is a linear description of this polytope using extra variables besides the variables in which the polytope is defined. The interest of extended formulations is due to the fact that many interesting polytopes have extended formulations with a lot fewer inequalities than any linear description in the original space. This motivates the development of methods for, on the one hand, constructing extended formulations and, on the other hand, proving lower bounds ...
-
作者：Georghiou, Angelos; Wiesemann, Wolfram; Kuhn, Daniel
作者单位：Massachusetts Institute of Technology (MIT); Imperial College London; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：Stochastic programming provides a versatile framework for decision-making under uncertainty, but the resulting optimization problems can be computationally demanding. It has recently been shown that primal and dual linear decision rule approximations can yield tractable upper and lower bounds on the optimal value of a stochastic program. Unfortunately, linear decision rules often provide crude approximations that result in loose bounds. To address this problem, we propose a lifting technique t...
-
作者：Gondzio, Jacek; Gonzalez-Brevis, Pablo
作者单位：University of Edinburgh; Heriot Watt University; Universidad del Desarrollo
摘要：This paper presents a new warmstarting technique in the context of a primal-dual column generation method applied to solve a particular class of combinatorial optimization problems. The technique relies on calculating an initial point and on solving auxiliary linear optimization problems to determine the step direction needed to fully restore primal and dual feasibilities after new columns arrive. Conditions on the maximum size of the cuts and on a suitable initial point are discussed. Additio...
