Informs 2015

213 / 552

INFORMS Philadelphia – 2015
211
2 - Generalizations of the Dominating Set Problem on
Social Networks
Raghu Raghavan, University of Maryland, Institute for Systems
Research, A. V. Williams Building, College Park, MD, 20742,
United States of America,
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
Kelly Sullivan, Assistant Professor, University of Arkansas,
Fayetteville, AR, 72701, , Sarah Nurre,
Matthew Robbins, Brian Lunday
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,
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,
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, , 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, 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
customer-oriented supply chain and disaster relief logistic.
4 - Hybridizing Meta-raps with Machine Learning
Fatemah Al-Duoli, Old Dominion University, Dep. of Eng.Mngt.
and Systems Eng., 5115 Hampton Blvd., Norfolk, VA, 23529,
United States of America, ,
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).
5 - Extending Time-to-target Plots to Test Sets with Multiple
Problem Instances
Celso Ribeiro, Universidade Federal Fluminense, Institute of
Computing, Niterói, Brazil, , 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.
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,
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,
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
Choat Inthawongse, Lehigh University/Ramkhamhaeng
University, 200 W Packer Ave., Bethlehem, PA, 18015,
United States of America, 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,
1 - Stage Aware Performance Modeling for Dag-based
Analytic Platforms
Min Li, Dr., IBM Research, United States of America,
, 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,
, 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.
MC20