2016 INFORMS Annual Meeting Program

SA14

INFORMS Nashville – 2016

SA13 104C-MCC Global Optimization: Algorithms and Applications Sponsored: Optimization, Global Optimization Sponsored Session Chair: Emily Speakman, University of Michigan, MI, United States, eespeakm@umich.edu 1 - Strong Relaxations For Optimal Power Flows Pascal Van Hentenryck, University of Michigan, pvanhent@umich.edu, Carleton Coffrin, Hassan Hijazi This talk reviews recent progress in convex relaxations of the power flow equations, which combines the SDP relaxation, the QC relaxations, bound tightening, and valid inequalities. Computational results on state-of-the-art benchmarks are presented. 2 - Branching Point Selection For Trilinear Terms Emily Speakman, University of Michigan, 2222 Fuller Court, Apt 702A, Ann Arbor, MI, 48105, United States, eespeakm@umich.edu, Jon Lee The case of having three or more expressions multiplied together (each expression being possibly complex itself) occurs frequently in global-optimization models. For these “trilinear terms,” we present some analytic results regarding the choice of branching point and branching variable in the context of spatial branch-and- bound, and we compare our results to common practice in software. In obtaining the “best” branching point or variable we use n-dimensional volume as a comparison measure. Using volume as a measure gives a way to analytically compare formulations and corresponds to a uniform distribution of the optimal solution across a relaxation. 3 - Virtuous Smoothing For Global Optimization. Daphne Skipper, US Naval Academy, daphne.skipper@gmail.com, Jon Lee Virtually all exact solvers for global-optimization (GO) rely on NLP solvers, both to generate good feasible solutions and to solve relaxations. Convergence of most NLP solvers requires that functions be twice continuously differentiable. Yet many models naturally utilize functions with some limited non-differentiability. One approach to handle limited non-differentiability is via smoothing. We propose a method, mostly aimed at (concave) root functions ($f(x)=x^p$, with $0

2 - High Communication Efficiency Subgraphs Vladimir Stozhkov, University of Florida, Gainesville, FL, United States, vstozhkov@ufl.edu, Alexander Veremyev, Oleg A Prokopyev We introduce a new clique relaxation model which is based on the notion of communication efficiency. The communication efficiency is assumed to be a non- increasing function of pair-wise distances in a graph. We prove that the corresponding maximization problem is NP-hard and present effective exact algorithms to solve it. 3 - Approximating The Maximum Edge Weight Clique Problem Using A Continuous Formulation Seyedmohammadhossein Hosseinian, Texas A&M University, 2027 Emerging Technologies Building, Mail stop 3131, College Station, TX, United States, hosseinian@tamu.edu, Dalila B M M Fontes, Sergiy Butenko The Maximum Edge Weight Clique (MEWC) problem, defined on an undirected and weighted graph, is to find a clique whose sum of edge weights is maximized. This work presents a continuous formulation for the MEWC problem, along with a heuristic based on solving the continuous form over a n dimensional hypersphere, where n is the number of vertices of the graph. Results of the algorithm on some benchmark instances are also presented. SA12 104B-MCC Algorithms, Polyhedra and Games Sponsored: Optimization, Integer and Discrete Optimization Sponsored Session Chair: Swati Gupta, Massachusetts Institute of Technology, Cambridge, MA, United States, swatig@mit.edu 1 - Algorithms For Stable Matching With Imperfect Transfer Of Utility (ITU) Rajan Harish Udwani, Massachusetts Institute of Technology, rudwani@mit.edu, James B Orlin The classical stable matching and utility transfer problems (also the dual of the assignment problem), are two extreme cases of the imperfect utility transfer problem, where we wish to find a stable matching in a bipartite graph, while allowing imperfect/lossy transfer of utility across matched pairs. In case of complete loss (or no transfer), we recover the former and in absence of loss we get the latter. We develop a novel combinatorial algorithm for this generalized stable matching problem under imperfect transfer of utility, when the loss function is linear. The model was inspired by a recent paper of Galichon et al. (2016). 2 - Polyhedral Study Of A Generalization Of The Continuous Mixing Set Haochen Luo, Texas A&M University, College Station, TX, United States, hcluo@tamu.edu, Kiavash Kianfar We report our progress on polyhedral study of a generalization of the continuous mixing set. We provide facet-defining valid inequalities and discuss how they can be used to generate cuts for well-known problems such as lot-sizing. 3 - Learning Combinatorial Structures Swati Gupta, Massachusetts Institute of Technology, Cambridge, MA, United States, swatig@mit.edu, Michel X Goemans, Patrick Jaillet To find optimal strategies for dueling algorithms, we consider two online learning methods: multiplicative weights update (MWU) and online mirror descent (OMD). We first show how to simulate MWU over vertices of polytopes in R^m (e.g. spanning trees, bipartite matchings), in time poly(m) under fast generalized counting oracles (even if approximate). Next, we solve a well-known computational bottleneck of computing projections for the OMD by giving novel algorithms for separable convex minimization over base polymatroids (e.g. for spanning trees, truncated permutations, subset of experts). These results extend to applications in stochastic optimization, game theory and machine learning.

21