2015 Informs Annual Meeting

WE16

INFORMS Philadelphia – 2015

WE17 17-Franklin 7, Marriott Networks and Graphs II Contributed Session

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, vahidn@uci.edu, 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.

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, iherszterg@inf.puc-rio.br 1 - Heuristic Procedures for K-Chinese Postman Problem with Workload Balancing

Yasemin Limon, Middle East Technical University, Industrial Engineering Department, Ankara, Turkey, yaseminlimon@gmail.com, Meral Azizoglu

WE16 16-Franklin 6, Marriott Optimization Large Scale I Contributed Session

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, l.castro6@umiami.edu, 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 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, iherszterg@inf.puc-rio.br, 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. Pavel Troubil, PhD Student, Masaryk University, Faculty of Informatics, Botanicka 68a, Brno, 60200, Czech Republic, pavel@troubil.cz

Chair: Sam Davanloo Tajbakhsh, Visiting Assistant Professor, Virginia Tech, 412 Hutcheson, Blacksburg, VA, 24060, United States of America, sdt144@vt.edu 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, zhangyuc@gmail.com 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, fmmuldo@sandia.gov, 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, sdt144@vt.edu, 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, yanm@math.ucla.edu, 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.

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, Partovi@Drexel.edu 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, paul.b.massell@census.gov 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.

484