2015 Informs Annual Meeting

MC20

INFORMS Philadelphia – 2015

2 - Generalizations of the Dominating Set Problem on Social Networks

5 - Extending Time-to-target Plots to Test Sets with Multiple Problem Instances Celso Ribeiro, Universidade Federal Fluminense, Institute of Computing, Niterói, Brazil, celso@ic.uff.br, Alberto Reyes Time-to-target plots (tttplots) or runtime distributions are a useful tool to characterize, evaluate, and compare the behavior of randomized algorithms. However, they are limited to the evaluation of one single problem instance at-a- time. In this work, we propose their extension to address sets of test problems with multiple instances. Numerical results for different problems illustrate the applicability and usefulness of the newly proposed m-tttplots tool.

Raghu Raghavan, University of Maryland, Institute for Systems Research, A. V. Williams Building, College Park, MD, 20742, United States of America, raghavan@rhsmith.umd.edu, Rui Zhang The positive influence dominating set problem is a generalization of the dominating set problem that arises on social networks. First, we show that it can be solved in linear time on trees. Next, we provide a tight and compact extended formulation, and derive a complete description of its polytope on trees. The formulation is also valid on general graphs, thus providing a new and stronger one. Facet defining conditions for the new inequalities are provided. A computational study is conducted. 3 - Flow Networks with Interdependent Commodities We model an extension of the minimum cost flow problem to a multi-layered network in which each layer is associated with a commodity that flows through the network. Nodes in this network must consume certain commodities before they are able to transport other commodities. We discuss model properties, solution approaches, and application of the model to characterize vulnerabilities in interdependent systems where disruptions may propagate across layers. MC18 18-Franklin 8, Marriott Optimization Metaheuristics Contributed Session Chair: Celso Ribeiro, Universidade Federal Fluminense, Institute of Computing, Niterói, Brazil, celso@ic.uff.br 1 - Healing the Achilles’ Heel: Finding and Preserving Feasibility in Evolutionary Algorithms Stephen Henry, Senior Member Technical Staff, Sandia National Labs, 7304 Laster Ave NE, Albuquerque, NM, 87109, United States of America, smhenry@sandia.gov Evolutionary algorithms can be powerful tools for optimizing discrete, multidimensional, nonlinear design problems. Finding or maintaining solution feasibility, however, is often an “Achilles’ heel” of these approaches - confounding genetic operators and stifling optimization progress. In this presentation, we give an overview of Sandia’s WSTAT genetic algorithm system design tool, the gene healing approaches that have been implemented, and the resulting improvements in algorithm performance. 2 - Heuristics for the Generalized Median Graph Problem Leonardo Musmanno, Universidade Federal Fluminense, Institute of Computing, Niteroi, Brazil, lmusmanno@ic.uff.br, Celso Ribeiro The graph edit distance is often used to measure the similarity between two graphs. The generalized median graph of S is any graph that minimizes the sum of the distances to all graphs in S. We propose two new heuristics for solving the generalized median graph problem: a greedy adaptive algorithm and a GRASP heuristic. Numerical results indicate that both heuristics can be used to obtain good approximate solutions for the generalized median graph problem. 3 - A Memetic Algorithm to Minimize Latency in Location-Routing Problems Mohammad Moshref-Javadi, School of Industrial Engineering, Purdue University, 315 N. Grant St., West Lafayette, IN, 47907, United States of America, moshref@purdue.edu, Seokcheon Lee Latency-Location Routing Problem determines the locations of depots and the routes of the vehicles aiming at minimizing waiting time of the customers. In this paper, we formulate the problem mathematically and propose an efficient Memetic Algorithm and compare it with a Granular Variable Neighborhood Search on different problems. The Latency-LRP has important applications in Fatemah Al-Duoli, Old Dominion University, Dep. of Eng.Mngt. and Systems Eng., 5115 Hampton Blvd., Norfolk, VA, 23529, United States of America, fateamah.aldouli@gmail.com, Ghaith Rabadi The performance of Meta-heuristics for Randomized Priority Search (Meta-RaPS) is improved by integrating a learning phase to its original construction and improvement phases. Information collected during the original Meta-RaPS phases is used by machine learning algorithms in the new learning phase. The proposed approach will be demonstrated using instances for the Capacitated Vehicle Routing Problem (CVRP). Kelly Sullivan, Assistant Professor, University of Arkansas, Fayetteville, AR, 72701, ksulliv@uark.edu, Sarah Nurre, Matthew Robbins, Brian Lunday customer-oriented supply chain and disaster relief logistic. 4 - Hybridizing Meta-raps with Machine Learning

MC19 19-Franklin 9, Marriott Tools for Optimization Modeling Sponsor: Computing Society Sponsored Session

Chair: Robert Fourer, President, AMPL Optimization Inc., 2521 Asbury Ave, Evanston, IL, 60201, United States of America, 4er@ampl.com 1 - The Surprising Difficulties of Supporting Quadratic Optimization in Algebraic Modeling Languages Robert Fourer, President, AMPL Optimization Inc., 2521 Asbury Ave, Evanston, IL, 60201, United States of America, 4er@ampl.com Algebraic modeling languages can readily convey quadratic functions to general nonlinear solvers, but support for recent quadratic extensions to mixed-integer linear solvers has proven much more challenging. The difficulty is due in part to the limited range of representations that solvers recognize and in part to the variety of transformations that must be considered. This presentation surveys the principal issues, and their implications for anyone building large-scale convex quadratic models. 2 - Modeling by Learning: The Problem Definition Repair Process United States of America, choat@lehigh.edu, George R. Wilson This research puts forward a framework for restructuring the problem and decision analysis template, representing an important extension to the cognitive computing systems, powered by IBM Watson. We develop an optimization model representation for model redefinition as a steppingstone toward creation of a decision support system motivated by cognitive computing. Broadening from the former models representation by Geoffrion as a semantic instrument for solution- method association state. MC20 20-Franklin 10, Marriott Modeling and Optimization of Big Data Systems Cluster: Cloud Computing Invited Session Chair: Li Zhang, IBM T. J. Watson Research Center, 1101 Kitchawan Road, Yorktown Heights, NY, 10598, United States of America, zhangli@us.ibm.com 1 - Stage Aware Performance Modeling for Dag-based Analytic Platforms Min Li, Dr., IBM Research, United States of America, minli@us.ibm.com, Li Zhang, Yangdong Wang In this presentation, we introduce a stage aware performance modeling tool for DAG based analytic platforms. The main idea of stage aware performance modeling is to divide the job execution flow into stages and derive the job execution time based on the DAG of the workflow to cope with the variances such as different program and job parameter configuration of the data analytic frameworks. 2 - The Power of Slightly More than One Sample in Randomized Load Balancing Xiaohan Kang, Associate Professor, Arizona State University, GWC 436, Tempe, AZ, 85287, United States of America, leiying07@gmail.com, R. Srikant, Lei Ying In this paper, we show that the number of sampled queues in randomized load balancing can be dramatically reduced by using the fact that tasks arrive in batches (called jobs). In particular, we sample a subset of the queues such that the size of the subset is slightly larger than the batch size, and equalize the load among the sampled servers. We show that our algorithm maintains the same asymptotic performance as the power-of-two-choices algorithm while using only half the number of samples. Choat Inthawongse, Lehigh University/Ramkhamhaeng University, 200 W Packer Ave., Bethlehem, PA, 18015,

211