-
作者：Pashkovich, Kanstantsin; Poirrier, Laurent; Pulyassary, Haripriya
作者单位：University of Waterloo
摘要：Recently, Bodur, Del Pia, Dey, Molinaro and Pokutta studied the concept of aggregation cuts for packing and covering integer programs. The aggregation closure is the intersection of all aggregation cuts. Bodur et al. studied the strength of this closure, but left open the question of whether the aggregation closure is polyhedral. In this paper, we answer this question in the positive, i.e., we show that the aggregation closure is polyhedral. Finally, we demonstrate that a generalization, the k...
-
作者：Morell, Sarah; Skutella, Martin
作者单位：Technical University of Berlin
摘要：In a digraph with a source and several destination nodes with associated demands, an unsplittable flow routes each demand along a single path from the common source to its destination. Given some flow x that is not necessarily unsplittable but satisfies all demands, it is a natural question to ask for an unsplittable flow y that does not deviate from x by too much, i.e., ya <= xa for all arcs a. Twenty years ago, in a landmark paper, Dinitz et al. (Combinatorica 19:17-41, 1999) proved that the...
-
作者：Straszak, Damian; Vishnoi, Nisheeth K.
作者单位：Yale University
摘要：We present a connection between two dynamical systems arising in entirely different contexts: the Iteratively Reweighted Least Squares (IRLS) algorithm used in compressed sensing and sparse recovery to find a minimum l(1)-norm solution in an affine space, and the dynamics of a slime mold (Physarum polycephalum) that finds the shortest path in a maze. We elucidate this connection by presenting a new dynamical system - Meta-Algorithm - and showing that the IRLS algorithms and the slime mold dyna...
-
作者：Dey, Santanu S.; Luedtke, James R.; Sahinidis, Nikolaos, V
作者单位：University System of Georgia; Georgia Institute of Technology; University of Wisconsin System; University of Wisconsin Madison; University System of Georgia; Georgia Institute of Technology
-
作者：Luo, Hao; Chen, Long
作者单位：Sichuan University; University of California System; University of California Irvine
摘要：Convergence analysis of accelerated first-order methods for convex optimization problems are developed from the point of view of ordinary differential equation solvers. A new dynamical system, called Nesterov accelerated gradient (NAG) flow, is derived from the connection between acceleration mechanism and A-stability of ODE solvers, and the exponential decay of a tailored Lyapunov function along with the solution trajectory is proved. Numerical discretizations of NAG flow are then considered ...
-
作者：Lu, Haihao
作者单位：University of Chicago
摘要：There has been a long history of using ordinary differential equations (ODEs) to understand the dynamics of discrete-time algorithms (DTAs). Surprisingly, there are still two fundamental and unanswered questions: (i) it is unclear how to obtain a suitable ODE from a given DTA, and (ii) it is unclear the connection between the convergence of a DTA and its corresponding ODEs. In this paper, we propose a new machinery-an O(s(r))-resolution ODE framework-for analyzing the behavior of a generic DTA...
-
作者：Yang, Haoxiang; Morton, David P.
作者单位：Northwestern University; The Chinese University of Hong Kong, Shenzhen
摘要：In this paper, we consider an optimization problem involving crashing an activity network under a single disruption. A disruption is an event whose magnitude and timing are random. When a disruption occurs, the duration of an activity that has yet to start-or alternatively, yet to complete-can change. We formulate a two-stage stochastic mixed-integer program, in which the timing of the stage is random. In our model, the recourse problem is a mixed-integer program. We prove the problem is NP-ha...
-
作者：Kis, Tamas; Horvath, Marko
摘要：In this paper we reconsider a known technique for constructing strong MIP formulations for disjunctive constraints of the form x is an element of boolean OR(m)(i=1) P-i, where the (P)i are polytopes. The formulation is based on the Cayley Embedding of the union of polytopes, namely, Q := conv(boolean OR(m)(i=1) P-i x {epsilon(i)}), where epsilon(i) is the ith unit vector in R-m. Our main contribution is a full characterization of the facets of Q, provided it has a certain network representatio...
-
作者：Zhao, Chen; Xiu, Naihua; Qi, Houduo; Luo, Ziyan
作者单位：Beijing Jiaotong University; University of Southampton
摘要：The sparse nonlinear programming (SNP) problem has wide applications in signal and image processing, machine learning and finance, etc. However, the computational challenge posed by SNP has not yet been well resolved due to the nonconvex and discontinuous to-norm involved. In this paper, we resolve this numerical challenge by developing a fast Newton-type algorithm. As a theoretical cornerstone, we establish a first-order optimality condition for SNP based on the concept of strong beta-Lagrang...
-
作者：Nohra, Carlos J.; Raghunathan, Arvind U.; Sahinidis, Nikolaos, V
作者单位：University System of Georgia; Georgia Institute of Technology; University System of Georgia; Georgia Institute of Technology
摘要：We consider the global optimization of nonconvex mixed-integer quadratic programs with linear equality constraints. In particular, we present a new class of convex quadratic relaxations which are derived via quadratic cuts. To construct these quadratic cuts, we solve a separation problem involving a linear matrix inequality with a special structure that allows the use of specialized solution algorithms. Our quadratic cuts are nonconvex, but define a convex feasible set when intersected with th...
