Informs Annual Meeting Phoenix 2018

INFORMS Phoenix – 2018

MB05

4 - The Subadditive Dual is a Strong Dual Diego Moran, Universidad Adolfo Ibañez, Santiago, 24060, Chile The subadditive dual of a conic mixed-integer program is a strong dual under a mixed-integer strict feasibility condition in the general case and rationality of the data in the linear case. In this talk, we present other sufficient conditions for strong duality. In particular, we show that strong duality holds if either the dual of the continuous relaxation or the subadditive dual are feasible. Moreover, we show that all known conditions imply dual feasibility. Finally, we present some duality results that use the concept of generator subadditive functions introduced by Klabjan (2007).

n MB03 North Bldg 121C TIMES Doctoral Dissertation Award Sponsored: Technology, Innovation Management & Entrepreneurship Sponsored Session Chair: Jeremy Hutchison-Krupat, University of Virginia, University of Virginia, Charlottesville, VA, 22901, United States 1 - Award Presenter Tristan Botelho, Yale University, New Haven, CT, USA. 2 - Three Essays on the Behavioral Foundations of Entrepreneurial Entry Cedric Gutierrez Moreno, Bocconi University, Milano, Italy. 3 - How to Improve Innovation Success: Customers, Employees, and the Search Process Philipp Benjamin Cornelius, Rotterdam School of Management, Rotterdam, Netherlands. 4 - Incentive Design of On-Demand Marketplaces for Service and Innovation Konstantinos Stouras, University of Virginia, The Darden School, Charlottesville, VA, USA 5 - Designing Internal Innovation Contests Lakshminarayana Nittala, University of Dayton, Dayton, OH, USA, Sanjiv Erat, Vish Krishnan Firms can use internal contests to source solutions to problems associated with innovation. However, designing such contests involves nuanced understanding of the impact of such contests on the on-going projects within the firm. Optimal contest design is discussed along with managerial implications. n MB04 North Bldg 122A Advances in IPCO Sponsored: Optimization/Integer and Discrete Optimization Sponsored Session Chair: Robert Hildebrand, Virginia Tech, VA, United States 1 - Short Construction for Bounded Pitch Inequalities for Set Covering and Minimum-knapsack Problems Daniel Bienstock, Columbia University, Dept of IEOR, 342 Mudd, New York, NY, 10027, United States It is known that all undominated, nontrivial valid inequalities for a set covering problem are of the form a^T x >= b, where a >= 0 and b> 0. Such an inequality is said to be of pitch k if the sum of the k smallest positive a is at least b, and k is smallest with regards to this property. In previous work, Bienstock and Zuckerberg described a compact extended relaxation for set covering problems that is guaranteed to satisfy all valid pitch <= k inequalities, for each fixed k. As a corollary, for any fixed p > 0 the rank-p Gomoroy closure of a set covering problem can be approximately optimized over, for any fixed p. In this talk we consider minimum knapsack problems, which are implicitly set covering problems, albeit with an exponential number of covering constraints. We show that for any fixed integer k > 0, there is polynomial-time near-separation routine for the relaxation provided by all valid inequalities with coefficients in {0, 1, 2, ..., k}. We discuss extensions and related problems. Joint work with Y. Faenza, I. Malinovic, M. Mastroilli, O. Svensson and M. Zuckerberg. 2 - Algorithms and Results for Multi-row Group Problems Robert Hildebrand, VIrginia Tech, 223 Durham Hall, 1145 Perry St, Blacksburg, VA, 24061, United States We study the 2-dimensional Infinite Group Problem and valid cut generating functions. We report on results and algorithms related to understanding these functions and determining their relative strength. 3 - Assessing Parametrized Linear Programming Relaxations with Superadditive Duality Temitayo Ajayi, Rice University, 2825 Bellefontaine Street #246A, Houston, TX, 77025, United States, Christopher Thomas, Andrew J. Schaefer The integer programming gap is a foundational concept in optimization. Because linear programming relaxations are vital in most integer programming algorithms, it is important to assess the accuracy of linear programs as approximations of integer programs. Studies on gap functions over the past half-century either use abstract algebraic techniques or do not provide exact bounds. We present superadditve dual-based formulations to compute various metrics of model quality based on gap functions. Our formulations evaluate families of models parametrized by right-hand sides from discrete sets or hyper-rectangles.

n MB05 North Bldg 122B

Conic Optimization in Machine Learning I Sponsored: Optimization/Linear and Conic Optimization Sponsored Session Chair: Xudong Li, Princeton University, Princeton, NJ, United States 1 - A Fast Globally Linearly Convergent Algorithm for the Computation of Wasserstein Barycenters Lei Yang, National University of Singapore, Singapore, Singapore, Jia Li, Defeng Sun, Kim-Chuan Toh In this paper, we consider computing a Wasserstein barycenter for a set of discrete distributions with finite supports. When the supports in the barycenter are prespecified, this problem can be modeled as a large-scale linear programming (LP). To solve this LP, we derive its dual problem and adapt a symmetric Gauss- Seidel based ADMM. We then analyze its global convergence and its global linear convergence rate without any condition. All subproblems involved can be solved exactly and efficiently. This makes our method suitable for large datasets. Numerical experiments on synthetic dataset and image dataset show that our method is more efficient than two existing representative methods and Gurobi. 2 - Multi-level Stochastic Gradient Methods for Nested Composition Optimization Shuoguang Yang, Columbia University, 500 West 120th Street, Room 315, New York, NY, 10027, United States, Mengdi Wang, Ethan Xingyuan Fang Stochastic gradient methods are scalable for solving large-scale optimization problems that involve empirical expectations of loss functions Existing results mainly apply to optimization problems where the objectives are one- or two-level expectations. We propose a class of multi-level stochastic gradient methods that are motivated from the method of multi-timescale stochastic approximation. 3 - Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents We consider the problem of fully decentralized multi-agent reinforcement learning (MARL), where the agents are located at the nodes of a time-varying communication network. For this problem,we propose two decentralized actor- critic algorithms with function approximation, which are applicable to large-scale MARL problems where both the number of states and the number of agents are massively large. Our algorithms are fully incremental and can be implemented in an online fashion. Convergence analyses of the algorithms are provided when the value functions are approximated within the class of linear functions. 4 - Geometry and Algorithms for Sparse Blind Deconvolution Yuqian Zhang, Columbia University, New York, NY, United States, Han-Wen Kuo, John Wright Blind deconvolution aims to recover a convolution kernel and an activation signal from their convolution.This talk focuses on the “short and sparse” variant, where the convolution kernel is short, and the activation signal is sparsely and randomly supported. We assume the kernel to have unit Frobenius norm, and formulate it as a nonconvex optimization problem over the sphere. By analyzing the optimization landscape, we argue that when the activation signal is sufficiently sparse, then on a region of the sphere, every local minimum is close to some shift truncation of the kernel. This geometric characterization implies that efficient methods obtain the ground truth under the same conditions. Zhuoran Yang, Princeton University, NJ, United States, Zhuoran Yang, Princeton University, Princeton, NJ, 08544, United States

149