2016 INFORMS Annual Meeting Program

98 / 561

INFORMS Nashville – 2016
98
3 - Low-complexity Relaxations And Convex Hulls Of Disjunctions On
The Positive Semidefinite Cone And General Regular Cones
Sercan Yildiz, Postdoctoral Researcher, Statistical and Applied
Mathematical Sciences Institute, Durham, NC, United States,
, Fatma Kilinc-Karzan
This talk concerns two-term disjunctions on a regular cone K. The resulting
disjunctive sets provide fundamental non-convex relaxations for mixed-integer
conic programs. We develop a family of structured convex inequalities which
together characterize the closed convex hull of such a set in the original space.
Under certain conditions on the choice of disjunction, a single inequality from
this family is enough for a closed convex hull description. In the case where K is
the positive semidefinite cone, we show that these inequalities can be represented
in conic form for a class of elementary disjunctions. For more general
disjunctions, we present tight conic relaxations.
SD13
104C-MCC
New Algorithms for Global Optimization and MINLP I
Sponsored: Optimization, Global Optimization
Sponsored Session
Chair: John W Chinneck, Carleton University, Ottawa, ON, Canada,
1 - Nonlinear Objective Decomposition By Binary Decision Diagrams
David Bergman, University of Connecticut,
, Andre Augusto Cire
In recent years the use of decision diagrams for discrete optimization has grown
in popularity, with a focus on linear integer optimization. In this talk, an
expansion to nonlinear objective functions will be discussed. The work proposes
the use of decision diagrams to model the objective function, which are then
linked together through a network flow linearization. Experimental results on
problems arising in revenue management, portfolio optimization, and healthcare
exhibit orders-of-magnitude improvement in solution times compared with state-
of-the-art nonlinear solvers.
2 - Identifying And Exploiting Special Features In Mixed Integer
Nonlinear Programs
Linus E Schrage, LINDO Systems, Inc.,
Most MINLP problems have the following features to varying degrees: convexity,
linearizability, conic representability, common expressions, monotonicity,
decomposability, and symmetry. We describe methods for identifying these
features and performance improvements possible by exploiting these features.
3 - A Fast Heuristic For Global Optimization
John Chinneck, Carleton University,
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 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. Recent work improves the initial point scatter to provide better
exploration of useful areas of the variable space. Our results are very promising in
comparison to several existing global optimizers, especially for larger nonconvex
models.
4 - A Dantzig-Wolfe Decomposition With Nonlinear Subproblems For
Recursive Circle Packing
Ambros Gleixner, Zuse Institute Berlin, Takustr. 7, Berlin, 14195,
Germany,
Stephen John Maher, Benjamin Müller, Joao Pedro Pedroso
A large fraction of the total costs in tube industry arises from delivery inside
rectangular containers. The problem of minimizing the number of containers to
transport a set of different tubes can be modeled as a nonconvex MINLP: the
recursive circle packing problem (RCPP), which is practically unsolvable for any
state-of-the-art MINLP solver.
We present a branch-and-price algorithm that handles recursiveness in the master
problem and solves nonconvex MINLPs for column generation. Our
computational results using the MINLP solver SCIP show that this algorithm
solves small-sized instances to proven optimality and produces better solutions
than the best known heuristic for larger RCPP instances.
SD14
104D-MCC
Big Data Analytics and Applications in E-Commerce
Sponsored: Analytics
Sponsored Session
Chair: Linwei Xin, U of Illinois at Urbana-Champaign, Urbana, IL,
12345, United States,
1 - A Nonparametric Sequential Test For Online Experiments
Vineet Abhishek, @WalmartLabs, Sunnyvale, CA, United States,
Shie Mannor
We propose a nonparametric sequential test that aims to address two practical
problems pertinent to online randomized experiments: (i) how to do hypothesis
test for complex metrics; (ii) how to prevent type $1$ error inflation under
continuous monitoring. The proposed test does not require knowledge of the
underlying probability distribution generating the data. We use the bootstrap to
estimate the likelihood for blocks of data followed by mixture sequential
probability ratio test. We validate this procedure on data from a major online e-
commerce website and show that the proposed test controls type $1$ error at any
time, has good power, and allows quick inference in online randomized
experiments.
2 - Implementing Tailored Base-surge Inventory Policies
At
Linwei Xin, U of Illinois at Urbana-Champaign,
John Bowman, Huijun Feng, Zhiwei Qin, Long He, Jagtej S Bewli
We consider the following dual-sourcing inventory problem: one supplier is
reliable but has a longer lead time; the other one is not always reliable but has a
shorter lead time. The objective is to minimize the inventory cost. We propose a
so-called Tailored-Base Surge policy. Under such a policy, a constant order is
placed at the slow supplier in each period, while the order placed at the fast
supplier follows an order-up-to rule. We test Tailored-Base Surge using data from
, where lead time differences of many import items could be as large
as 12 periods. Our result shows that Tailored-Base Surge outperforms other
heuristics such as dual-index and single-sourcing base-stock policies.
SD15
104E-MCC
High Dimensional Data Analysis via an
Optimization Lens
Invited: Modeling and Methodologies in Big Data
Invited Session
Chair: Dimitris Bertsimas, Massachusetts Institute of Technology,
Cambridge, MA, 1, United States,
1 - Optimal Classification Trees
Jack Dunn, Operations Research Center, MIT,
Decision trees are widely used to solve the classical statistical problem of
classification. We introduce a new method for constructing optimal decision trees
using Mixed-Integer Optimization, and develop high-performance heuristics for
these formulations that offer significant improvements over traditional greedy
approaches and run in comparable times. We show in a large and diverse
collection of synthetic and real-world instances that our Optimal Classification
Trees improve substantially over CART and related methods such as Random
Forests.
2 - Sparse High-dimensional Regression: Exact Scalable Algorithms
And Phase Transitions
Bart van Parys, Operations Research Center, MIT,
We present a new binary convex reformulation and duality perspective to the
sparse regression problem. We devise a novel cutting plane method and provide
evidence that it can solve exact sparse regression problems for problem sizes in
the 100,000s. Our sparse regression formulation has the property that as the
number of samples increases its exact solution recovers the true signal very fast
(faster than the Lasso in fact), while for small sample sizes, our approach takes a
large amount of time to solve the problem, but most importantly the optimal
solution does not recover the true signal.
3 - Compressed Sensing Via A Modern Optimization Lens
Lauren Berk, Operations Research Center, MIT,
We develop tractable algorithms that provide provably optimal solutions to
compressed sensing problems. These methods include new first order methods
and a cutting planes method that operates in a reduced variable space, preserving
tractability as problem sizes grow.
SD13