Informs Annual Meeting 2017

MC74

INFORMS Houston – 2017

3 - Approximating an Integer Linear Program by Structured Prediction Models Emma Frejinger, Université de Montréal, FAS, Pavillon Andre-Aisenstadt, Montreal, QC, H3C 3J7, Canada, emma.frejinger@cirrelt.ca, Eric Larsen, Yoshua Bengio, Simon Lacoste-Julien, Andrea Lodi We consider an operational planning problem for which we have an ILP that can be solved in reasonable time using a commercial solver. We propose to learn a structured prediction model that allows to compute approximate solutions to the ILP in very short computational time. We generate data by simulating problem instances and computing the corresponding solutions to the ILP. We can hence control the characteristics of the data and its size can be as large as the computational budget allows. The input to the structured model defines the problem instance and the output its solution. The structured prediction model is part of the solution methodology to a tactical service network design problem. 4 - LP-based Misclassification Minimization John W. Chinneck, Carleton University, Systems and Computer Engineering, 1125 Colonel By Drive, Ottawa, ON, K1S.5B6, Canada, chinneck@sce.carleton.ca Placing a separating surface that misclassifies the minimum number of points can be cast as an instance of maxFS, the problem of finding the maximum subset of constraints that can be simultaneously satisfied in an infeasible linear program. Fast and effective heuristics for maxFS can thus be used to construct classifiers. These algorithms also allow for selecting features while placing the separator, and can guide the placement for purposes such as equalizing the prediction accuracies, protecting minority types, etc. 372C Mixed-integer Two-stage Optimization Methodology and Applications Sponsored: Computing Sponsored Session Chair: Leonardo Lozano, Clemson University, Clemson, SC, 29631, Gokce Kahvecioglu, Northwestern University, Evanston, IL, United States, GokceKahvecioglu2014@u.northwestern.edu, David Morton We study a clustering problem defined on an undirected graph with nonnegative weights on the edges. We remove a subset of edges to break the graph into smaller pieces, i.e., clusters. We incur a cost based on the weight of edges that are removed, and we obtain a gain in terms of the number of clusters we form. We consider the model from a bi-criteria perspective, and we aim to construct a family of solutions minimizing cost while maximizing gain. 2 - Vector-valued Multivariate Conditional Value-at-risk Simge Kucukyavuz, University of Washington, Box 352650, Industrial & Systems Engineering, Seattle, WA, 98195, United States, simge@uw.edu, Merve Merakli In this study, we propose a new definition of multivariate conditional value-at- risk (MCVaR) as a set of vectors for discrete probability spaces. We explore the properties of the vector-valued MCVaR (VMCVaR) and show the advantages of VMCVaR over the existing definitions given for continuous random variables when adapted to the discrete case. Finally, we discuss optimization of problems involving multivariate CVaR. 3 - Generalized Benders’ Algorithm for Mixed Integer Bilevel Linear Optimization Suresh Bolusani, Lehigh University, Bethlehem, PA, United States, sub214@lehigh.edu, Ted Ralphs Mixed integer bilevel linear optimization provides a framework for modeling optimization problems involving multiple, independent decision makers with multiple, possibly conflicting objectives. In this talk, we present a generalized Benders’ algorithm for solving these problems. As with any Benders’ algorithm, the strategy is to project out the second-stage variables to obtain a reformulation involving only first-stage variables. This reformulation involves the value function of the bilevel optimization problem resulting from fixing the first-stage variables, which is then iteratively approximated. We present preliminary computational results with an open-source implementation. 4 - Robust Optimization with Evacuation Transportation under Boudedly Rationality User Equilibrium Guanxiang Yun, University of Central Florida, Orlando, FL, 32816, United States, ygx8822@knights.ucf.edu, Qipeng Zheng We proposed several models for the transportation path problems. We supposed that all the users in the system will obey the bounded rational user equilibrium principle. In real world instances, people will feel just fine even if they do not reach the best utility they can get but only attain a certain level. We proposed United States, llozano@g.clemson.edu 1 - Optimal Clustering on a Graph MC74

totally four conditions for our models with two of them having the pricing strategy, which will have a robust optimization model. We solved it by using the column and constraint generation. And Because of the huge number of variables and constraints we have in our system, we still used the column generation for the variables and also check the most violation constraint to check the convergency.

MC75

372D Interactions of Optimization and Statistical Learning II Sponsored: Optimization, Nonlinear Programming Sponsored Session

Chair: Ethan Xingyuan Fang, Pennsylvania State University, University Park, PA, 16802, United States, xxf13@psu.edu Co-Chair: Zhaoran Wang, Princeton University, Princeton, NJ, 08540, United States, zhaoran@princeton.edu 1 - Variance Reduction for Restricted Strong Convexity Huan Xu, Georgia Institute of Technology, Industrial and Systems Engineering, Atlanta, GA, 30332, United States, huan.xu@isye.gatech.edu, Chao Qu Computational challenges of statistical estimators and machine learnng algorithms are an active area of study. Stochastic first order methods based on variance reduction have attracted significant attention because of light computation load for each iteration, and fast convergence speed for strongly convex problems. Yet, many powerful statistical and machine learning models are not strongly convex, and sometimes even non-convex. In this talk, I will argue that a nice statisitical property of those problems - restricted strong convexity - ensures that linear convergence of variance reduced stochastic first order methods for those statistical models. 2 - Taming Nonconvexity with Data Zhaoran Wang, Princeton University, Apt 302, 13 Lawrence Drive, Princeton, NJ, 08540, United States, zhaoran@princeton.edu In this talk, I will illustrate how statistical thinking enables us to harness the power of nonconvex optimization. In specific, I will present an algorithmic framework for exploiting the latent geometry induced by the randomness of data. By integrating three new global exploration meta-algorithms — namely, homotopy continuation, tightening after relaxation, and noise regularization — with local search heuristics — such as the variants of gradient descent — this unified framework leads to new nonconvex optimization algorithms for a broad variety of challenging learning problems. 3 - Gradient Descent Converges to Local Minimizers Jason Lee, University of Southern California, San Marino, CA, United States, jasondlee88@gmail.com We show that saddlepoints are easy to avoid for even Gradient Descent — arguably the simplest optimization procedure. We prove that with probability 1, randomly initialized Gradient Descent converges to a local minimizer. Next we show that gradient descent takes exponential time to converge to a local minimizer with Gaussian initialization, yet stochastic gradient or trust-region method take only polynomial time. This is joint work with Max Simchowitz, Ben Recht, Michael Jordan, Simon Du, Chi Jin, Barnabos Poczos, and Aarti Singh. 4 - Non-stationary Streaming PCA Apurv Shukla, Columbia University, New York City, NY, United States, as5197@columbia.edu, Daniel Bienstock, Seyoung Yun Motivated by rapidly changing dynamics of energy systems and poor performance of machine learning algorithms in non-stationary noisy environments, we present a novel memory-limited streaming algorithm to track time-varying subspaces for detecting anomalies. Our main theoretical contribution includes a novel proof- technique for analyzing convergence of the algorithm. Our algorithm uses low storage memory and shows promising results as compared to other existing algorithms.

230