Informs Annual Meeting 2017

WA77

INFORMS Houston – 2017

WA76

WA77

372E Rounding: Methods and Applications Sponsored: Optimization, Integer and Discrete Optimization Sponsored Session Chair: Arash Asadpour, New York University, New York University, New York, NY, 10012, United States, aasadpou@stern.nyu.edu 1 - Assignment Mechanismsunder Distributional Constraints Shameli Ali, Stanford University, Stanford, CA, 94305, United States, shameli@stanford.edu, Itai Ashlagi, Amin Saberi We study the allocation of heterogeneous positions to agents under distributional constraints. Each agent has a public type, and a private ranking over positions. The goal is to find a Pareto efficient assignment that maximizes the number of assigned agents. A natural benchmark is the solution of a linear programming relaxation that allows agents to be assigned to positions fractionally. We introduce a mechanism that achieves this goal while violating each constraint by a small number. This mechanism is strategyproof if agents’ acceptable positions are public. We also propose a weakly strategyproof mechanism that improves upon Rakesh Vinay Vohra, University of Pennsylvania, Economics Department, 3718 Locust Walk, Philadelphia, PA, 19104, United States, rvohra@sas.upenn.edu, Nguyen Thanh The problem of finding stable matches that meet distributional concerns is usually formulated by imposing various side constraints. Prior work has focused on constraints whose ``right hand sides’’ are absolute numbers specified before the preferences or number of agents on the ``proposing’’ side are known. In many cases it is more natural to express the relevant constraints as proportions. We treat such constraints as soft, but provide ex-post guarantees on how well the constraints are satisfied while preserving stability. Our technique requires an extension of Scarf’s lemma, which is of independent interest. 3 - Approximate Random Allocation Mechanisms Akbarpour Mohammad, Stanford University, Stanford, CA, United States, mohamwad@stanford.edu We extend the scope of random allocation mechanisms, in which the mechanism first identifies a feasible “expected allocation” and then implements it by randomizing over nearby feasible integer allocations. Previous literature had shown that the cases in which this is possible are sharply limited. By constructing a new rounding algorithm, we show that if some of the feasibility constraints can be treated as “goals” rather than hard constraints then, subject to weak conditions that we identify, any expected allocation that satisfies all the constraints and goals can be implemented by randomizing among nearby integer allocations that satisfy all the hard constraints exactly and the goals approximately. By defining ex post utilities as goals, we are able to improve the ex post properties of several classic assignment mechanisms, such as the random serial dictatorship. 4 - A Primal-dual Framework for Decomposition and Rounding Methods in Assemble-to-order Systems Levi DeValve, Duke University, 716 Turmeric Lane, Durham, NC, 27713, United States, levi.devalve@duke.edu, Sasa Pekec, Yehua Wei We develop a primal-dual framework that allows a systematic approach to assessing heuristic performance in hard integer programs, and apply it to the assemble to order (ATO) problem. Our high level approach is to: (i) solve a relaxation to obtain a dual solution, (ii) construct a primal solution from the relaxation, and (iii) use our primal-dual framework to provide approximation guarantees. We demonstrate the versatility of our approach by analyzing various ATO heuristics within a unified primal-dual framework. In particular, for ATO, we provide performance bounds for LP rounding schemes and newsvendor decompositions, as well as insights into issues driving performance. the first mechanism by finding an ordinally efficient assignment. 2 - Stable Matching with Proportionality Constraints

372F Optimization, Integer Programming Contributed Session Chair: Marco Luebbecke, RWTH Aachen University, Aachen, Germany, marco.luebbecke@rwth-aachen.de 1 - Mixed-integer Quadratic Optimization Formulations for Eliminating Multicollinearity based on Variance Inflation Factor Yuichi Takano, Senshu University, Kawasaki, Japan, ytakano@isc.senshu-u.ac.jp, Ryuta Tamura, Ken Kobayashi, Ryuhei Miyashiro, Kazuhide Nakata, Tomomi Matsui The variance inflation factor, VIF, is the most frequently used indicator for detecting multicollinearity in multiple linear regression models. This talk presents mixed-integer quadratic optimization formulations for selecting the best subset of explanatory variables under upper-bound constraints on VIF of selected variables. Computational results illustrate the effectiveness of our optimization formulations Tony Rodriguez, University of Tennessee, Knoxville, TN, 37996, United States, trodrig5@vols.utk.edu, Olufemi Omitaomu, Jim Ostrowski As the number and severity of snowfall events continue to grow, the need to intelligently direct road maintenance during these snowfall events will also grow. In several locations, local governments lack the resources to completely treat all roadways during snow events. As a result, many schools, businesses, and government offices must be unnecessarily closed, which directly impacts the social, educational, and economic well-being of citizens and institutions. In this work, we propose a mixed integer programming formulation to optimally allocate resources to manage snowfall on roads using meteorological, geographical, and environmental parameters. 3 - Mathematical Programming for Regression Subset Selection with Diagnostic Constraints Seokhyun Chung, Korea University, Korea Univ. New Engineering Many existing algorithms for regression subset selection focus on minimizing objective function such as sum of squared errors (SSE). However, it is also important to satisfy all underlying assumptions and diagnostics of linear regression. In this paper, we propose a mixed integer quadratic programming model to minimize SSE and satisfy regression assumptions and diagnostics. A procedure is also proposed to obtain near-feasible solutions when a solution satisfying all constraints cannot be easily found. A computational study is provided with real-world data. 4 - Sparse Classication: A Discrete Optimization Perspective Jean Pauphilet, PhD Candidate, Massachusetts Institute of Technology, 77 Massachusetts Avenue, Building E40-103, Cambridge, MA, 02139, United States, jpauph@mit.edu, Dimitris Bertsimas, Bart Paul Gerard Van Parys In this paper, we formulate the sparse classification problem as a mixed-integer convex optimization problem and propose a cutting-plane algorithm to solve it exactly. For sparse logistic regression and sparse SVM our algorithm finds optimal solutions for n and p in the 10,000s within minutes. If there is enough data, the algorithm is fast, accurately detects all the true features and returns no false features. In contrast, Lasso persistently returns incorrect ones, even as the number of observations increases. Finally, we apply our method in genomics. Sparse classification returns a classifier based on 32 genes only, while Lasso selects 172 with a similar predictive accuracy. 5 - Learning When to Use a Decomposition Marco Luebbecke, Professor, RWTH Aachen University, Operations Research, Kackertstr. 7, Aachen, D-52072, Germany, marco.luebbecke@rwth-aachen.de, Markus Kruber, Axel Parmentier Applying a Dantzig-Wolfe decomposition to a mixed-integer program (MIP) aims at exploiting an embedded model structure. Recently, automating the process and embedding it in standard MIP solvers have been proposed, with the detection of a decomposable model structure as key element. If the detected structure reflects the (usually unknown) actual structure of the MIP well, the solver may be much faster on the reformulated model than on the original. We propose a supervised learning approach to decide whether or not a reformulation should be applied. First numerical experiments show a significant performance improvement on structured instances, with little deterioration on others. Building, 214, Seongbuk-gu, Seoul, Korea, Republic of, csh98016@gmail.com, Young Woong Park, Taesu Cheong based on comparisons with conventional local search algorithms. 2 - Modeling Road Vulnerability to Snow using Mixed Integer Optimization

469