2016 INFORMS Annual Meeting Program

SD13

INFORMS Nashville – 2016

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, lxin@illinois.edu 1 - A Nonparametric Sequential Test For Online Experiments Vineet Abhishek, @WalmartLabs, Sunnyvale, CA, United States, vineet.abhishek@gmail.com, 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 Walmart.com Linwei Xin, U of Illinois at Urbana-Champaign, lxin@illinois.edu 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 Walmart.com, 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, dbertsim@mit.edu 1 - Optimal Classification Trees Jack Dunn, Operations Research Center, MIT, jackdunn@mit.edu 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, vanparys@mit.edu 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, lberk@mit.edu 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.

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, syildiz@email.unc.edu, 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, chinneck@sce.carleton.ca 1 - Nonlinear Objective Decomposition By Binary Decision Diagrams David Bergman, University of Connecticut, david.bergman@business.uconn.edu, 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., linus.schrage@chicagobooth.edu 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, chinneck@sce.carleton.ca, 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, gleixner@zib.de 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.

98