2015 Informs Annual Meeting

MC13

INFORMS Philadelphia – 2015

MC11 11-Franklin 1, Marriott Symmetry and Extended Formulations in Integer Programming Sponsor: Optimization/Integer and Discrete Optimization Sponsored Session Chair: Sebastian Pokutta, Georgia Tech, 755 Ferst Drive, NW, Atlanta, GA, 30332, United States of America, sebastian.pokutta@isye.gatech.edu Co-Chair: Daniel Zink,Georgia Tech, 755 Ferst Drive, NW, Atlanta GA 30332, United States of America, zink.dani@gmail.com 1 - Strong Mixed-integer Formulations for the Floor Layout Problem Joey Huchette, MIT, 77 Massachusetts Avenue, Bldg. E40-149, communication costs between the components. This work presents a framework for generating mixed-integer formulations for the FLP by “encoding” a union of polyhedra in a higher dimensional space. We present theoretical and computational evidence for the strength of the resulting formulations and valid inequalities. 2 - Detecting Almost Symmetries of Graphs Bernard Knueven, University of Tennessee, 851 Neyland Dr, Knoxville, TN, 37996, United States of America, bknueven@vols.utk.edu, Sebastian Pokutta, Ben Knueven We present a branching framework to solve the following problem. Given a graph G and an integer k, find the symmetries on subgraphs of G formed by removing no more than k edges. We call such symmetries ``k-almost symmetries’’ of G. We specialize the framework and present and implement a branch-and-bound algorithm to find the best such subgraph for a given k. Computational results are reported, showing that for some popular graphs, few edges need be removed to induce additional symmetry. 3 - LP and SDP Inapproximability of Combinatorial Problems Daniel Zink, Georgia Tech, 755 Ferst Drive, NW, Atlanta, GA, 30332, United States of America, zink.dani@gmail.com, Sebastian Pokutta, Gábor Braun Motivated by [arXiv:1309.0563], we provide a framework for studying the size of LP formulations as well as SDP formulations of combinatorial optimization problems without encoding them first as linear programs. As a result we define a consistent reduction mechanism that degrades approximation factors in a controlled fashion. As a consequence we establish strong linear programming inapproximability (for LPs with a polynomial number of constraints) for several problems that are not 0/1-CSPs. 4 - Maximizing a Class of Utility Functions Over the Vertices of a Polyhedron Andres Gomez, PhD Student, University of California at Berkeley, Cambridge, MA, 02139, United States of America, huchette@mit.edu, Juan Pablo Vielma, Santanu Dey The floor layout problem (FLP) asks a designer to position a collection of rectangular boxes on a fixed floor in such a way that minimizes total

Our CCGO multistart heuristic trades off some accuracy to gain speed. It generally finds good quality solutions quickly. The main steps are a latin hypercube scatter of initial points, rapid movement towards feasibility via Constraint Consensus, clustering, simple point improvement, and local solver launch. Much of the work is done concurrently. Our results are very promising in comparison to several existing global optimizers, especially for larger nonconvex models. 2 - A Mixed Integer Nonlinear Program for Remote Hybrid Energy System Design and Dispatch Michael Scioletti, Colorado School of Mines, 1500 Illinois Street, Golden, CO 80401, United States of America, msciolet@mymail.mines.edu, Alexandra Newman Our remote hybrid energy system design and dispatch problem is a non-convex, mixed-integer nonlinear program that determines the optimal mix of technologies (generators, batteries, and solar panels) and their dispatch to minimize system costs. Constraints meet load and satisfy operational rules. Most notably, we model the batteries in some detail. Linearization techniques yield near-optimal solutions to instances containing real data over a yearly horizon at hourly fidelity in a matter of hours. 3 - Which Programming Language should you choose for your Optimization Project? Bjarni Kristjansson, President, Maximal Software Inc., 2111 Wilson Boulevard, Suite 700, Arlington VA 22201, United States of America, bjarni@maximalsoftware.com When working on real-world optimization projects which are intended to be deployed for end-users, it is often not enough to use just a modeling language with a state-of-the-art solver. To implement user-interfaces, data preparation, and integrating the optimization solution into an easy-to-use application, you will typically have to use also a programming language. In this presentation, we will compare the pros and cons between popular programming languages, such as C/C++, CSharp, Visual Basic, Java, and Python. MC13 13-Franklin 3, Marriott Robustness in Optimization, Complementarity, and Queueing systems Sponsor: Optimization/Optimization Under Uncertainty Sponsored Session Chair: Uday Shanbhag, The Pennsylvania State University, 310 Leonhard Building, University Park, PA, 16801, United States of America, udaybag@engr.psu.edu 1 - On Robust Solutions to Uncertain Linear Complementarity Problems and Their Variants Yue Xie, Research Assistant, PSU IE, 351 Leonhard Building, University Park, PA, 16802, United States of America, xieyue1990@gmail.com, Uday Shanbhag Complementarity problems have been well studied in modeling optimization and equilibrium problems. Yet, less progress has been seen in the uncertain context. We present an avenue for obtaining robust solutions to uncertain linear complementarity problems in a distribution-free environment by solving a low- dimensional program. Particularly, robust solutions to uncertain non-monotone LCPs are provided by customizing an existing scheme. Preliminary numerics suggest that such avenues hold promise. 2 - Percentile Optimization in Multi-class Queuing Systems with Parameter Ambiguity Austin Bren, PhD Student, Arizona State University, 1537 East Palmdale Drive, Tempe, AZ, 85282, United States of America, hasbren@gmail.com, Soroush Saghafian In a multi-class queuing system that experiences system ambiguity through unknown service rate parameters, we incorporate robustness in control policies by applying a novel percentile optimization technique that allows for the expression of a controller’s optimism level and utilizes incoming data to learn the true system parameters. We identify structural results of the optimal policy and use our technique in a hospital emergency department application using data from Mayo clinic. 3 - A Convexity Result for Nonlinear Gaussian Chance Constraints Miles Lubin, MIT, 77 Massachusetts Avenue, E40-149, Cambridge, MA, 02139, United States of America, miles.lubin@gmail.com, Juan Pablo Vielma, Daniel Bienstock We present an extension of the well-known convexity result for linear chance constraints under Gaussian uncertainty. We derive an exact convex reformulation for certain nonlinear chance constraints, together with a tractable SOCP formulation with provable approximation guarantees. We apply these results to tackle a more challenging chance constraint which arises from nonlinear power flow equations.

4141 Etcheverry Hall, University of California Berkeley, Berkeley, CA, 94720-1777, United States of America, a.gomez@berkeley.edu, Alper Atamturk

Given a polyhedron, a concave univariate function g, and two vectors c and d, we consider the optimization problem of finding a vertex that maximizes the function c’ x + g(d’ x), which is NP-hard. We propose a 1/2-approximation algorithm. Improved approximation ratio of 4/5 is given for specific cases in project scheduling and reinforcement learning. Computational experiments indicate that the suggested approach finds solutions within 1% of the optimal solution for most of the instances quickly.

MC12 12-Franklin 2, Marriott

Global Optimization: Algorithms and Applications Sponsor: Optimization/Mixed Integer Nonlinear Optimization and

Global Optimization Sponsored Session

Chair: John Chinneck, Professor, Carleton University, Systems and Computer Engineering, 1125 Colonel By Drive, Ottawa, ON, K1S5B6, Canada, chinneck@sce.carleton.ca” 1 - CCGO: A Fast Heuristic Global Optimizer John Chinneck, Professor, Carleton University, Systems and Computer Engineering, 1125 Colonel By Drive, Ottawa, ON, K1S5B6, Canada, chinneck@sce.carleton.ca, Mubashsharul Shafique

209