Informs Annual Meeting 2017

WC72

INFORMS Houston – 2017

WC72

WC74

372A Optimization, Combinatorial Contributed Session Chair: Yaping Wang, University of Houston, Houston, TX, United States, ypwang@uh.edu 1 - Data-driven Two-stage Adaptive Optimization: A Multi-policy Approach Shimrit Shtern, Postdoctiral Associate, Massachusetts Institute of Technology, 77 Massachusetts Ave., E40-154, Cambridge, MA, 02139, United States, sshtern@mit.edu, Dimitris Bertsimas, Bradley E. Sturt Consider a general two-stage linear problem with uncertainty. In real life, historical data is available and can be used to estimate future uncertainty. We propose a novel approach to the problem of two-stage adaptive optimization, in which we find multiple recourse policies that fit a data-driven uncertainty set. Our framework generates a tractable model (e.g., SOCP) that can also incorporate integer variables. We prove the framework has finite and asymptotic optimality guarantees, and show that it empirically performs better than existing methods on out-of-sample data. 2 - Forecasting the Workload with a Hybrid Model to Reduce the Inefficiency Cost Xinwei Pan, University of Kentucky, Lexington, KY, United States, bluebridge1905@163.com Operating Room managers want to allocate the block time to surgical groups according to an accurate estimation of workload. If overestimating the workload, it generates idle time, which is a waste of resources; if underestimating the workload, it generates over-utilize cost. To avoid these two cases, we construct a hybrid model combining Auto-Regressive Integrated Moving Average with Artificial Neural Networks, and a filter structure is integrated to obtain more accurate and stable prediction values when applied to multi-steps-ahead forecasting. Case studies with data from the University of Kentucky HealthCare indicate that our model outperforms other models in different conditions. 3 - A Predictor-corrector Algorithm for Projection-based Derivative-free Optimization Ishan Bajaj, PhD Student, Texas A&M.University, 503 Cherry St., College Station, TX, 77840, United States, ishan.bajaj@tamu.edu, Faruque Hasan We present a derivative-free method to minimize a general black-box function f(x), where xL ≤ x ≤ xU Rn, by projecting the original objective function onto a one-dimensional t-space given by linear combination of xi. We identify a special function G(t) which is the lower envelope of all the objective function values on t-space. We propose a projection-correction algorithm to find the minima of G(t) since it also corresponds to the minima of f(x). The algorithm is applied to a suite of more than 400 test problems and performs superior relative to model based solvers such as ORBIT and SNOBFIT. 4 - From Predictions to Prescriptions in Multistage Optimization Problems Christopher G. McCord, Massachusetts Institute of Technology, Cambridge, MA, United States, mccord@mit.edu, Dimitris Bertsimas In this paper, we introduce a framework for solving multistage optimization problems under uncertainty in the presence of auxiliary data. We assume the distribution of the uncertainties is unknown, but samples from this distribution, along with observations of auxiliary covariates, are available. We utilize effective predictive machine learning methods, including nearest neighbor regression and random forests, to develop specific methods for prescribing decisions. We demonstrate that our methods are asymptotically optimal, and we establish finite sample guarantees. Finally, we demonstrate the practicality of our approach with computational examples. 5 - Matching Two-resolution Metrology Data with Symmetric Features Yaping Wang, Instructional Assistant Professor, University of Houston, 4722 Calhoun drive, Houston, TX, 77204, United States, ypwang@uh.edu, Erick Moreno-Centeno, Yu Ding Research showed combining two metrology datasets with different resolutions makes better surface feature predictions of manufactured parts. The goal is to match the two datasets with arbitrary initial misalignment. A two-stage matching framework (TSMF) was previously developed to solve real-life problems efficiently. However, TMSF can lead to incorrect correspondences for part surfaces with symmetric features because the alignment performance metrics of TSMF cannot differentiate between correct correspondences and incorrect but seemingly correct ones. To solve this, a filtering procedure is proposed to select a correct solution from a properly generated pool of plausible candidates.

372C Solution Approaches for Bilevel Programming and Interdiction Problems Sponsored: Computing Sponsored Session Chair: Osman Yalin Ozaltin, North Carolina State University, Raleigh, NC, 27695, United States, oyozalti@ncsu.edu 1 - The Shortest Path Interdiction Problem with Hidden Arcs: Network Interdiction with Asymmetric Info Timothy Holzmann, Clemson University, SC, United States, tholzma@g.clemson.edu Network interdiction problems frequently assume that both attacker and follower have full knowledge of the network. We present the shortest path interdiction problem with hidden arcs (SPIP-HA). In the SPIP-HA, the competing objectives have a common formulation but vary a parameter in the inner problem constraints, which results in competing objective function values. After presenting the theoretical considerations of a Stackelberg game with asymmetric information, we consider solution techniques for Pareto front of the SPIP-HA. 2 - A Branch-and-cut Algorithm for Mixed Integer Bilevel Linear Optimization Problems and its Implementation Sahar Tahernejad, Lehigh University, Bethlehem, PA, United States, sat214@lehigh.edu We describe a comprehensive algorithmic framework for solving mixed integer bilevel linear optimization problems (MIBLPs) by a generalized branch-and-cut approach. The framework presented merges features from existing algorithms (for both traditional mixed integer optimization and MIBLPs) with new techniques to produce a flexible and robust framework for solving bilevel optimization problems. The framework has been fully implemented in the open source solver MibS. We also describe the algorithmic options offered by MibS and present computational results evaluating the effectiveness of the various options for the solution of a number of classes of instances from the literature. 3 - A Branch-and-cut Algorithm for Discrete Bilevel Linear Programs We present a branch-and-cut algorithm for solving bilevel linear programs where the upper-level variables are all binary and the lower-level variables are all integral or all binary. The algorithm iteratively performs local search in the neighborhood of an upper-level solution and generates cuts to eliminate upper- level solutions that have been explored. Instead of repeatedly solving similar bilevel integer problems in the local search, we derive properties of the value functions of bilevel integer programs and propose three algorithms for constructing them. Preliminary computational results show that our solution approach can solve instances with up to 200 variables and 150 constraints. 4 - Bilevel Optimization Models and Risk-averse Decision Making Deniz Eskandani, Rutgers University, Piscataway, NJ, 08904, United States, deniz.eskandani@rutgers.edu, Jonathan Eckstein We describe a bilevel programming technique to time-consistently formulate 3- stage stochastic programs without using nested risk measures. We apply our technique to applications in portfolio optimization and scheduling of a hydrothermal generating system, and compare our results with standard approaches. 372D Operations/Sustainability Contributed Session Chair: Ling-Fei Cai, Beijing Institute of Technology, Beijing, China, 461714207@qq.com 1 - Understanding Concepts of Proactive Services and Cases Youngmi Han, Korea University Business School, 408 LG- POSCO.building, Korea University, Anam-ro, Seongbuk-gu, Seoul, 02804, Korea, Republic of, 55835729@hanmail.net, Chulok Ahn, Hosun Rhim Customer needs are constantly increasing. While reactive behavior of enterprise does not satisfy the changing customer needs, proactive behavior prevents potential problems and creates values. We define proactive services, and classify them into three types. We introduce companies that have implementing proactive services. Junlong Zhang, North Carolina State University, Apt 102, 3515 Ivy Commons Dr, Raleigh, NC, 27606, United States, jzhang56@ncsu.edu WC75

528