2016 INFORMS Annual Meeting Program

MC12

INFORMS Nashville – 2016

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, chinneck@sce.carleton.ca 1 - Coordination Between Constraint Filtering Techniques And Reduced RLT Representations In RLT-POS Evrim Dalkiran, Wayne State University, evrimd@wayne.edu 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, vahidn@uci.edu, 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, nploskas@andrew.cmu.edu, 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, mkilinc@cmu.edu, 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, juan.ma@turner.com 1 - Scheduling Television Programs Optimally Juan Ma, Turner Broadcasting System, Inc., Atlanta, GA, 30318, United States, juan.ma@turner.com, 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.

2 - Randomized Network Inspection For Security Against Link Disruption Attacks Mathieu Dahan, Massachusetts Institute of Technology, Cambridge, MA, United States, mdahan@mit.edu, 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, ydyang@ucdavis.edu, 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, robdhildebrand@gmail.com 1 - New Certificates For Nonnegativity Via Circuit Polynomials And Geometric Programming Timo de Wolff, Texas A&M University, dewolff@math.tamu.edu 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, agupte@clemson.edu, 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, santanu.dey@isye.gatech.edu 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.

186