Informs 2015

481 / 552

INFORMS Philadelphia – 2015
484
5 - Generalizing Shifting Quadratic Envelopes for Solving
Non-convex Routing Problem
Vahid Nourbakhsh, PhD Student, UC Irvine, The Paul Merage
School of Business, The Paul Merage School of Business,
Irvine, CA, 92697, United States of America,
John Turner
We will study routing of jobs to service centers. Jobs arrive to job nodes each
node with different arrival rate and there can be more than one server at a service
center. The service time depends on the job node to which the job arrives and the
service center. The objective is maximizing the total number of jobs that are
served without any delay upon arrival. We analyze the convexity of this problem
and propose an outer-approximation method to solve the problem.
WE16
16-Franklin 6, Marriott
Optimization Large Scale I
Contributed Session
Chair: Sam Davanloo Tajbakhsh, Visiting Assistant Professor, Virginia
Tech, 412 Hutcheson, Blacksburg, VA, 24060, United States of America,
1 - Communication-efficient Distributed Optimization of
Self-concordant Empirical Loss
Yuchen Zhang, PhD Student, University of California, Berkeley,
495 Soda Hall, Berkeley, CA, 94709, United States of America,
We consider distributed convex optimization where each machine has access to a
local loss function constructed with i.i.d. data. We propose a communication-
efficient distributed algorithm to minimize the overall loss function. We show that
in a standard setting for supervised learning, the required number of
communication rounds of the algorithm does not increase with the sample size,
and only grows slowly with the number of machines.
2 - Formulation of a New Complex Fleet Modernization Problem for
the Capability Portfolio Analysis Tool
Frank Muldoon, Sandia National Laboratories, P.O. Box 5800 MS
1188, Albuquerque, NM, 87185-1188, United States of America,
Matthew Hoffman, Stephen Henry
The Capability Portfolio Analysis Tool(CPAT)(2015 Edelman Finalist) is currently
being used to model the fleet of logistics and support systems under the U.S.
Army PEO Combat Support & Combat Service Support to provide analytical
capability in support of modernization and investment decisions. Initially, this
MILP modeled the Army’s Ground Combat Systems but the formulation has since
evolved to meet the challenges posed by the CS&CSS fleet such as system age,
recapitalization, and its large size
3 - A Provable Two-Stage Algorithm for Fitting Gaussian
Process Models
Sam Davanloo Tajbakhsh, Visiting Assistant Professor,
Virginia Tech, 412 Hutcheson, Blacksburg, VA, 24060,
United States of America, , Enrique Del Castillo,
Necdet Serhat Aybat
Fitting Gaussian Process models and finding the Maximum Likelihood Estimate
(MLE) of the parameters requires a nonconvex optimization. The problem is
aggravated in big data settings since the computational complexity of the MLE is
O(n^3) where n is the number of distinct locations at which the process is
observed. We proposed a theoretically provable two-stage algorithm which solves
a semidefinite program in the first stage and a least square problem in the second
stage.
4 - A Framework of Asynchronous Parallel Algorithms for Monotone
Inclusions and Optimization
Ming Yan, Assistant Professor, Michigan State University,
220 Trowbridge Rd, East Lansing, MI, 48824, United States of
America, Wotao Yin, Zhimin Peng,
Yangyang Xu
We propose a framework of async-parallel algorithms for finding a fixed point to a
nonexpansive operator by multiple uncoordinated agents (e.g., nodes, CPUs, CPU
cores). Each time, an agent updates a random (block) coordinate of the variables.
There is no global timing or memory locking. Its sequence converges to a fixed
point almost surely. Special-case async-parallel algorithms are proposed for linear
equations and distributed convex optimization problems.
WE17
17-Franklin 7, Marriott
Networks and Graphs II
Contributed Session
Chair: Ian Herszterg, Pontifícia Universidade Católica do Rio de Janeiro,
Rua Marquês de São Vicente, 225, Gávea, Rio de Janeiro RJ 22451-
900, Brazil,
1 - Heuristic Procedures for K-Chinese Postman Problem with
Workload Balancing
Yasemin Limon, Middle East Technical University,
Industrial Engineering Department, Ankara, Turkey,
Meral Azizoglu
This study considers the k-Chinese Postman Problem. The problem can be defined
as the assignment of each postman to a set of arcs so as to cover all arcs at least
once and guarantee feasible routes that start and terminate at the depot. Our aim
is to assign the arcs to the postman so as to balance their workloads as much as
possible. We define heuristic procedures that involve construction and
improvement mechanisms. We find that our procedures find high quality
solutions in reasonable times.
2 - The Dynamics of Stochastic Opinions
Luis Castro, PhD Student - Research Assitant, University of
Miami, Department of Industrial Engineering, 268 McArthur
Engineering Building, Coral Gables, Fl, 33146, United States of
America, Nazrul Shaikh
We model the dynamics of stochastic opinions and derive a set of conditions for
global and local consensus. Our results suggest that new opinions are more likely
to be adopted if they belong to the intersection set of consensus distributions
between groups.
3 - Multigroup Multicast Routing for High-quality
Interactive Multimedia
Pavel Troubil, PhD Student, Masaryk University, Faculty of
Informatics, Botanicka 68a, Brno, 60200, Czech Republic,
In tight runtime limits, we solve multigroup multicast routing problem for
interactive collaboration over high-quality multimedia: with on-the-fly
recompression of video for per-user adaptation of content quality, and under
uncertain network topology and capacity. We react dynamically to network
events and request changes, and minimize path perturbation. Our ant colony
optimization heuristic is applied for sign-language interpretation in university
education or live broadcasts of sport events.
4 - Phase Unwrapping: Attacking the Problem with
Operations Research
Ian Herszterg, Pontifícia Universidade Católica do Rio de Janeiro,
Rua Marquís de São Vicente, 225, Gávea, Rio de Janeiro, RJ,
22451-900, Brazil, Marcus Poggi,
Thibaut Vidal
We propose a new model for L0-norm 2D Phase Unwrapping (2DPU). We
associate the discontinuities of the wrapped phase image (residues) to a graph,
where the vertices have different polarities (+1/-1), and seek a minimum cost
balanced spanning forest where the sum of polarities is equal to zero in each tree.
We propose a branch-and-cut algorithm and a population metaheuristic to
address the problem, leading to an efficient approach for L0-norm 2DPU, viewed
as “highly desirable” but intractable.
WE18
18-Franklin 8, Marriott
Optimization Linear Programming
Contributed Session
Chair: Fariborz Partovi, Professor, Drexel University, 33rd Chestnut
Street, Department of Decision Sciences, Philadlphia, PA, 19003,
United States of America,
1 - O.R. Optimization Methods as Used for Protecting Statistical Data
Paul Massell, Mathematical Statistician, U.S. Census Bureau,
4600 Silver Hill Road, Room 6H130F, Washington, DC, 20233,
United States of America,
Magnitude data tables are used by agencies for displaying economic data. These
tables are additive; i.e., for each set of rows, a sum row is also given (same for
columns). Sensitive cells are determined based on a dominance rule; such cells
are suppressed. To prevent values of sensitive cells from being recovered,
secondary suppressions are found using a L.P. model. This LP is a heuristic for the
true I.P. model. We also discuss ways to protect cells using noise.
WE16