2015 Informs Annual Meeting

MA21

INFORMS Philadelphia – 2015

MA19 19-Franklin 9, Marriott Distributed and Parallel Optimization Sponsor: Computing Society Sponsored Session

MA20 20-Franklin 10, Marriott Resource Allocation in Cloud Computing Cluster: Cloud Computing Invited Session

Chair: Mohammad Javad Feizollahi, Assistant Professor of Business Analytics, Robinson College of Business, 35 Broad St. NW, Room 1109, Georgia State University, Atlanta, GA, 30303, United States of America, mfeizollahi@gsu.edu 1 - Object-parallel Solution of Large-scale Lasso Problems Gyorgy Matyasfalvi, Doctoral Candidate, Rutgers University, 100 Rockafeller Road, Piscataway, NJ, 08854, United States of America, matyasfalvi@gmail.com, Jonathan Eckstein We describe an “object-parallel” C++ approach to implementing first-order optimization methods. Using a “symbolic temporaries” technique to improve operator overloading efficiency, high-performance parallel algorithms may be expressed with MATLAB-like simplicity. As an example application, we solve large-scale Lasso problems on a distributed-memory supercomputer with the spectral projected gradient (SPG) method. We can efficiently accommodate highly unbalanced sparsity patterns. 2 - Decentralized Mixed Integer Programming Mohammad Javad Feizollahi, Assistant Professor of Business Analytics, Robinson College of Business, 35 Broad St. NW, Room 1109, Georgia State University, Atlanta, GA, 30303, United States of America, mfeizollahi@gsu.edu, Shabbir Ahmed We propose a decentralized mixed integer programming (MIP) approach based on adding primal cuts and restricting the Lagrangian relaxation of the original MIP problem. A key challenge is that, because of the non-convex nature of MIPs, classical distributed and decentralized optimization approaches cannot be applied directly to find their optimal solutions. We test the proposed method on the unit commitment problem and discuss its pros and cons comparing to the central MIP approach. 3 - Dealing with Asynchrony and Information Delays in Parallel Optimization Hamid Reza Feyzmahdavian, PhD Student, Royal Institute of Technology (KTH), Osquldas Väg 10, Floor 6, Stockholm, 10044, Sweden, hamidrez@kth.se, Arda Aytekin, Mikael Johansson This talk presents an asynchronous and parallel mini-batch algorithm for regularized stochastic optimization problems that allows multiple workers to work at different rates and perform computations independently of each other. Several examples are worked out to demonstrate that the impact of asynchrony on the convergence rate of the algorithm is asymptotically negligible, and a near-linear speedup in the number of workers can be expected. 4 - Deep Learning with Auxiliary Coordinates, with an Application to Fast Image Search Miguel Carreira-Perpinan, Associate Professor, University of California, Merced, 5200 N. Lake Road, Merced, CA, 95343, United States of America, mcarreira-perpinan@ucmerced.edu, Ramin Raziperchikolaei Many nonconvex problems in machine learning arise from nested functions consisting of nonlinear processing layers, such as deep neural nets. We describe a generic technique to train such models, the method of auxiliary coordinates. This introduces significant parallelism in the optimization, is easy to implement by reusing existing algorithms, and can handle nonsmooth layers. We illustrate it with a binary hashing application involving an intermediate layer of binary variables. 5 - Decentralized Approximation Methods for Potential Games under Exogenous Uncertainty Harikrishnan Sreekumaran, PhD Candidate, Purdue University, 315 N Grant St., West Lafayettee, IN, 47906, United States of America, harikrishnan.sreekumaran@gmail.com, Andrew Liu We consider computing Nash equilibria of certain classes of games under exogenous uncertainty and analyze distributed algorithms for solving such problems. We establish convergence of parallel Gauss-Jacobi and sequential Gauss-Seidel type methods, when combined with approximation schemes such as Monte Carlo sampling. Implementation schemes and numerical results for the proposed approach are presented for applications such as traffic routing and network design games.

Chair: Yuan Zhong, Columbia University, 500 W. 120th Street, New York, NY, 10027, United States of America, yz2561@columbia.edu 1 - Massively Parallel Queueing Networks Mariana Olvera-Cravioto, Associate Professor, Columbia University, New York, NY, 10027, United States of America, mo2291@columbia.edu We study a network with many parallel servers where jobs are split into a number of pieces to be processed in parallel on a random subset of servers, with the constraint that all pieces of a job must be processed in a synchronized fashion. We discuss an analytically tractable model where all fragments of a job must initiate their service at the same time and compare it to the one where the synchronization occurs at the end, as in MapReduce. We also compare it against the optimal routing model. 2 - Heavy-traffic Behavior of the Maxweight Algorithm in a Switch with Uniform Traffic Siva Theja Maguluri, Postdoctoral Researcher, IBM TJ Watson Research Center, 1101 Kitchawan Road, Yorktown Heights, NY, 10598, United States of America, smagulu@us.ibm.com, R. Srikant We consider a switch with uniform traffic operating under the MaxWeight scheduling algorithm. This traffic pattern is interesting to study in the heavy- traffic regime since the queue lengths exhibit a multi-dimensional state-space collapse. We characterize the heavy-traffic behavior of the expectation of the sum queue lengths in steady-state and show that MaxWeight algorithm has optimal queue-length scaling behavior with respect to the size of a switch. This settles an open conjecture. 3 - Flexible Queueing Architectures Kuang Xu, Stanford University, Stanford, CA, United States of America, kuangxu@stanford.edu, John Tsitsiklis We consider a service system with n independent job streams and n servers, where each server can only serve a relatively small number, d, of job streams. We wish to design a service architecture so that the system has as large a capacity region as possible, and a scheduling policy under which queueing delays become vanishingly small as the system size, n, increases. We show that our objective can be accomplished by combining an expander graph architecture and a batching policy. MA21 21-Franklin 11, Marriott Public Health and Health System Modeling Sponsor: Health Applications Sponsored Session Chair: Stan Finkelstein, MIT, 1 Amherst Street, Cambridge, MA, 01773, United States of America, snfinkel@mit.edu 1 - Engineering Effective Responses to Influenza Outbreaks Stan Finkelstein, MIT, 1 Amherst Street, Cambridge, MA, 01773, United States of America, snfinkel@mit.edu, Richard Larson, Karima Nigmatulina, Anna Teytelman The year 2009 witnessed a worldwide flu pandemic. Our questions: In the absence of vaccines, what steps can be taken to reduce the chance of becoming infected? When vaccines arrive late, what allocation policy will minimize the number who become infected? We discuss how to reduce the exponential growth factor by hygiene and social distancing behaviors, and recommend a data-driven adaptive vaccine allocation policy that, if used in 2009, might have reduced infections in the U.S. by five million. 2 - A Stochastic Programming Approach to Reduce Patient Wait Times and Overtime in an Outpatient Infusion Center Jeremy Castaing, University of Michigan, IOE 1205 Beal Ave., Ann Arbor, MI, United States of America, jctg@umich.edu, Amy Cohn, Brian Denton Chemotherapy infusion treatments for cancer have significant and unpredictable variability in duration. We present an algorithm for designing patient appointment schedules under uncertainty in treatment times. The objective is to minimize a trade-off between expected patient wait times and expected total time required to treat patients. Computational experiments based on real-world data are presented and used to draw managerial insights.

151