Informs 2015

153 / 552

INFORMS Philadelphia – 2015
151
MA19
19-Franklin 9, Marriott
Distributed and Parallel Optimization
Sponsor: Computing Society
Sponsored 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,
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, , 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, 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, , 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, ,
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, , 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.
MA20
20-Franklin 10, Marriott
Resource Allocation in Cloud Computing
Cluster: Cloud Computing
Invited Session
Chair: Yuan Zhong, Columbia University, 500 W. 120th Street, New
York, NY, 10027, United States of America,
1 - Massively Parallel Queueing Networks
Mariana Olvera-Cravioto, Associate Professor, Columbia
University, New York, NY, 10027, United States of America,
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,
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, , 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,
1 - Engineering Effective Responses to Influenza Outbreaks
Stan Finkelstein, MIT, 1 Amherst Street, Cambridge, MA, 01773,
United States of America, , 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, ,
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.
MA21