Informs 2015

211 / 552

INFORMS Philadelphia – 2015
209
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,
Co-Chair: Daniel Zink,Georgia Tech, 755 Ferst Drive, NW, Atlanta GA
30332, United States of America,
1 - Strong Mixed-integer Formulations for the Floor Layout Problem
Joey Huchette, MIT, 77 Massachusetts Avenue, Bldg. E40-149,
Cambridge, MA, 02139, United States of America,
, 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
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,
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, ,
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,
4141 Etcheverry Hall, University of California Berkeley,
Berkeley, CA, 94720-1777, United States of America,
, 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,
1 - CCGO: A Fast Heuristic Global Optimizer
John Chinneck, Professor, Carleton University, Systems and
Computer Engineering, 1125 Colonel By Drive, Ottawa, ON,
K1S5B6, Canada,
Mubashsharul Shafique
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,
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,
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,
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,
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,
, 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,
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.
MC13