2016 INFORMS Annual Meeting Program

186 / 561

INFORMS Nashville – 2016
186
2 - Randomized Network Inspection For Security Against Link
Disruption Attacks
Mathieu Dahan, Massachusetts Institute of Technology,
Cambridge, MA, United States,
Polina Sela Perelman, Saurabh Amin
We consider a network inspection game, in which a defender collects state
measurements at few nodes of the network to detect simultaneous link
disruptions by an attacker. The defender’s objective is to maximize the detection
score and the attacker’s objective is to maximize the missed detection rate. Both
players face budget constraints. We study the mixed Nash equilibria of this game
in terms of the defender’s inspection capabilities and the network structure. We
characterize the player strategies using a generalization of the minimum vertex
cover and the maximum matching of the network.
3 - A Stochastic Programming Unified Framework For Travel Demand
Estimation Problems With Multiple Observation Sets
Yudi Yang, University of California, Davis, Davis, CA, United
States, Yueyue Fan, Roger J-B Wets
This paper proposes a unied framework of modeling Origin-Destination (O-D)
demand estimation problems in transportation networks using multiple
observation sets. Unlike traditional approaches that aim at either parameter
estimation or reconstruction, our approach employs a hierarchical structure to
integrate both problems. This proposed framework has a great flexibility to
incorporate various data input and domain knowledge.
MC12
104B-MCC
Mixed Integer Polynomial Optimization
Sponsored: Optimization, Integer and Discrete Optimization
Sponsored Session
Chair: Robert Hildebrand, IBM T.J. Watson Research Cente
r, 206 Chateau Rive, Peekskill, NY, 10566, United States,
1 - New Certificates For Nonnegativity Via Circuit Polynomials And
Geometric Programming
Timo de Wolff, Texas A&M University,
Deciding nonnegativity of real polynomials is a fundamental problem in
polynomial optimization. In practice, one uses semidefinite programming (SDP),
which is based on sums of squares (SOS) certificates, the standard certificates
since the 19th century.
We introduce an entirely new class of nonnegativity certificate based on circuit
polynomials, which are independent of SOS. Similar as SOS correspond to SDP
our certificates correspond to geometric programming (GP). Our certificates yield
GPs which compute lower bounds both for unconstrained and constrained
polynomial optimization problems efficiently. Our approach is significantly faster
and often provides better bounds than SDPs.
2 - Analysis Of Strength Of Convex Relaxations Of Monomials
Akshay Gupte, Clemson University, Clemson, SC, 29634,
United States, Warren P Adams, Yibo Xu
Convexifying each monomial in a polynomial optimization problem yields a
lower bound on the global optimum. The quality of this lower bound and the
additive error on the global optimum can be quantified by analyzing the
approximation error produced by the closure convex hull of each monomial. For
any monomial whose domain is a subset of [0,1]^n, we give degree-dependent
upper bounds on this approximation error. Special structures of the domain for
which our bounds are tight are also analyzed. For a multilinear monomial, we
refine this bound for the [1,r]^n case and also give a formula for the [-1,1]^n
case.
3 - Optimal Power Flow Problem
Santanu Dey, Georgia Institute of Technology,
The AC optimal power flow (OPF) problem is a key polynomial optimization
problem in the area of electrical power systems operations. We present a few
families of cutting-planes to strengthen the standard SOCP relaxation of this
problem. Extensive computational experiments show that these relaxations have
numerous advantages over existing convex relaxations.
MC13
104C-MCC
New Algorithms for Global Optimization and MINLP II
Sponsored: Optimization, Global Optimization
Sponsored Session
Chair: John W Chinneck, Carleton University, 1125 Colonel By Drive,
Ottawa, ON, K1S 5B6, Canada,
1 - Coordination Between Constraint Filtering Techniques And
Reduced RLT Representations In RLT-POS
Evrim Dalkiran, Wayne State University,
Hanif D. Sherali
RLT-POS is a Reformulation-Linearization Technique (RLT)-based open-source
optimization software for solving polynomial optimization problems. RLT-POS
theoretically filters standard bound-factor constraints to obtain tractable
relaxations. Using linear equality subsystem, RLT-POS generates reduced sized LP
relaxations. In this talk, we discuss the coordination between constraint filtering
techniques and reduced RLT representations for sparse polynomial programming
problems.
2 - A Global Optimization Algorithm For Routing Heterogeneous Jobs
To Heterogeneous Servers
Vahid Nourbakhsh, PhD Candidate, University of California -
Irvine, Irvine, CA, 92617, United States,
John G Turner
The problem of routing heterogeneous jobs to heterogeneous servers with job-
server dependent service rates arises in different applications. We formulate the
problem as a math problem which allows us to use the general framework of
math programming to embed the problem into planning problems. For the
objective functions of maximizing service level and minimizing average waiting
time, the problem is non-convex. We develop an optimization algorithm called
fixed-ratio shifting envelopes (FSE) to find the global optimal solution and
compare its performance against the global solver BARON.
3 - Tuning Baron Using Derivative-free Optimization Algorithms
Nikolaos Ploskas, Carnegie Mellon University, Pittsburgh, PA,
United States, Jianfeng Liu,
Nikolaos Sahinidis
Optimization solvers include many options that allow users to control different
aspects of them. All previous proposed methods for tuning optimization solvers
options have focused on MILP and local NLP solvers. A total of 27 derivative-free
optimization algorithms are used on a set of 126 benchmark problems to find the
optimal values for the options of the global optimization solver BARON. Detailed
computational results will be presented.
4 - Recent Advances In Baron
Mustafa Kilinc, Carnegie Mellon University, Pittsburgh, PA,
United States, , Nikolaos Sahinidis
In this talk, we provide a brief account of key software engineering and
algorithmic developments in BARON and discuss recent advances that result in
dynamic solution strategies aimed to provide tight relaxations for solving difficult
problems, and present extensive computational results on a collection of
benchmarks.
MC14
104D-MCC
Emerging Applications of Optimization in Industry
Sponsored: Analytics
Sponsored Session
Chair: Juan Ma, Turner Broadcasting Systems, 1050 Techwood Drive
NW, Atlanta, GA, 30318, United States,
1 - Scheduling Television Programs Optimally
Juan Ma, Turner Broadcasting System, Inc., Atlanta, GA, 30318,
United States, Jose Antonio Carbajal Orozco,
Peter Williams, Wassim (Wes) Chaar
Deciding a television program schedule that generates the highest viewer ratings
is critical and challenging for professionals in the media industry. In this study, we
developed a novel analytical model for optimal television program scheduling.
Our model combines program rating predictions during different time slots of a
scheduling window with a shortest path problem under resource constraints.
Solution techniques and preliminary experiment results will also be discussed.
MC12