-
作者：Chakrabarty, Deeparnab; Devanur, Nikhil R.; Vazirani, Vijay V.
作者单位：University of Waterloo; Microsoft; University System of Georgia; Georgia Institute of Technology
摘要：Determining the integrality gap of the bidirected cut relaxation for the metric Steiner tree problem, and exploiting it algorithmically, is a long-standing open problem. We use geometry to define an LP whose dual is equivalent to this relaxation. This opens up the possibility of using the primal-dual schema in a geometric setting for designing an algorithm for this problem. Using this approach, we obtain a 4/3 factor algorithm and integrality gap bound for the case of quasi-bipartite graphs; t...
-
作者：Geunes, Joseph; Levi, Retsef; Romeijn, H. Edwin; Shmoys, David B.
作者单位：Massachusetts Institute of Technology (MIT); State University System of Florida; University of Florida; University of Michigan System; University of Michigan; Cornell University; Cornell University
摘要：We propose generalizations of a broad class of traditional supply chain planning and logistics models that we call supply chain planning and logistics problems with market choice. Instead of the traditional setting, we are given a set of markets, each specified by a sequence of demands and associated with a revenue. Decisions are made in two stages. In the first stage, one chooses a subset of markets and rejects the others. Once that market choice is made, one needs to construct a minimum-cost...
-
作者：Dey, Santanu S.
作者单位：Universite Catholique Louvain
摘要：In this note, we present a simple geometric argument to determine a lower bound on the split rank of intersection cuts. As a first step of this argument, a polyhedral subset of the lattice-free convex set that is used to generate the intersection cut is constructed. We call this subset the restricted lattice-free set. It is then shown that [log(2)(l)] is a lower bound on the split rank of the intersection cut, where l is the number of integer points lying on the boundary of the restricted latt...
-
作者：Bao, Xiaowei; Sahinidis, Nikolaos V.; Tawarmalani, Mohit
作者单位：Carnegie Mellon University; University of Illinois System; University of Illinois Urbana-Champaign; Purdue University System; Purdue University
摘要：At the intersection of nonlinear and combinatorial optimization, quadratic programming has attracted significant interest over the past several decades. A variety of relaxations for quadratically constrained quadratic programming (QCQP) can be formulated as semidefinite programs (SDPs). The primary purpose of this paper is to present a systematic comparison of SDP relaxations for QCQP. Using theoretical analysis, it is shown that the recently developed doubly nonnegative relaxation is equivale...
-
作者：Hemmecke, Raymond; Onn, Shmuel; Weismantel, Robert
作者单位：Otto von Guericke University; Technion Israel Institute of Technology
摘要：In this paper we consider the solution of certain convex integer minimization problems via greedy augmentation procedures. We show that a greedy augmentation procedure that employs only directions from certain Graver bases needs only polynomially many augmentation steps to solve the given problem. We extend these results to convex N-fold integer minimization problems and to convex 2-stage stochastic integer minimization problems. Finally, we present some applications of convex N-fold integer m...
-
作者：Kiwiel, K. C.
作者单位：Polish Academy of Sciences; Systems Research Institute of the Polish Academy of Sciences
摘要：We give a bundle method for minimizing the sum of two convex functions, one of them being known only via an oracle of arbitrary accuracy. Each iteration involves solving two subproblems in which the functions are alternately represented by their linearizations. Our approach is motivated by applications to nonlinear multicommodity flow problems. Encouraging numerical experience on large scale problems is reported.
-
作者：Nesterov, Yurii
摘要：In this paper we develop a new affine-invariant primal-dual subgradient method for nonsmooth convex optimization problems. This scheme is based on a self-concordant barrier for the basic feasible set. It is suitable for finding approximate solutions with certain relative accuracy. We discuss some applications of this technique including fractional covering problem, maximal concurrent flow problem, semidefinite relaxations and nonlinear online optimization. For all these problems, the rate of c...
-
作者：Recht, Benjamin; Xu, Weiyu; Hassibi, Babak
作者单位：University of Wisconsin System; University of Wisconsin Madison; California Institute of Technology
摘要：Minimizing the rank of a matrix subject to constraints is a challenging problem that arises in many applications in machine learning, control theory, and discrete geometry. This class of optimization problems, known as rank minimization, is NP-hard, and for most practical problems there are no efficient algorithms that yield exact solutions. A popular heuristic replaces the rank function with the nuclear norm-equal to the sum of the singular values-of the decision variable and has been shown t...
