Informs Annual Meeting Phoenix 2018

INFORMS Phoenix – 2018

WD01

Wednesday, 3:20PM - 4:50PM

segment which cannot be violated by the vehicle. Moreover, it is assumed that the vehicle has to arrive at the destination on or before a given time-limit. We propose a mixed-integer second order cone programming formulation for the problem and evaluate its performance. Effects of some valid inequalities are also investigated. 2 - Isolation Branching: A Branch and Bound Algorithm for the K-terminal Cut Problem Mark Velednitsky, Univeristy of California-Berkeley, Berkeley, CA, United States The k-terminal cut problem is: Given an edge-weighted graph with k terminals, remove a minimum weight collection of edges such that there is no path between any pair of terminals. The problem is NP-hard. Although it has multiple applications, no optimization algorithms have been devised specifically for the problem. We present the first branch-and-bound optimization algorithm customized for k-terminal cut. The performance of our algorithm is demonstrated to be practical for a number of real-world instances. As a by-product, we prove that the complexity of Isolation Branching is fixed-parameter tractable with respect to the size of the optimal solution. 3 - Learner Demand-driven School Timetabling Ayse Aslan, University of Groningen, Nettelbosje 2, Groningen, 9747 AE, Netherlands Personalized learning in secondary schools in Netherlands offers flexibility for learners to create their own learning paths by choosing which learning activities they want every week. This leads to the emergence of demand-driven timetables in schools. We propose an integrated IP model to produce weekly demand-driven timetables for learners and teachers simultaneously. Joint Session OPT/Practice Curated: SCIP Optimization Suite: Recent Developments and Applications Sponsored: Optimization/Computational Optimization and Software Sponsored Session Chair: Ambros Gleixner, Zuse Institute Berlin, Berlin, 14195, Germany Co-Chair: Benjamin Mueller, Zuse Institute Berlin, Berlin, 12161, Germany 1 - Reinforcement Learning of Branching Strategies Maxime Gasse, Polytechnique Montr al, Montr al, QC, Canada, Andrea Lodi Branching decisions arguably take a central place in traditional branch-and- bound solvers. We formulate the branching problem as a 1-player game, whose ending is triggered once the instance has been solved, and where the goal is to minimize the final tree size. Under this formalism, one can use reinforcement learning to find good branching strategies, e.g. using a mix of Monte-Carlo Tree Search and deep learning (the AlphaGo approach). We will present some preliminary results on MIPLIB instances, based on an implementation that combines the SCIP and PyTorch libraries. 2 - Digging for Variable Holes in MINLPs Benjamin Mueller, Zuse Institute Berlin, Berlin, 12161, Germany, Andrea Lodi, Gonzalo Munoz Due to the presence of nonconvex constraints in mixed-integer nonlinear programs (MINLPs), the set of feasible assignments can be disconnected even for continuous variables. The resulting forbidden regions for variables are called “holes”, which can be viewed as a generalization of integrality conditions in MILP. This allows us to conceive methods for continuous variables that so far have been mainly developed for integer variables. We study the concept of holes and their importance in a spatial branch-and- bound framework. Additionally, we show that a branching rule driven by the knowledge of holes in a nonconvex problem can have a significant impact on the performance of the MINLP solver SCIP. 3 - A Branch and Price Approach for an Inventory and Routing Problem to Address the Replenishment of a Network of Automated Teller Machines Cristian Eduardo Cortes, Universidad de Chile, Blanco Encalada 2002, Santiago, Chile, Daniel Herl, Pablo Andres Rey, Alejandro Cataldo, Leandro C. Coelho The main goal of this study is to develop a Branch and Price method for the inventory-routing problem arising from the replenishment of an automated teller machines (ATM) network. One interesting feature of the problem is the existence of out of stocks in the inventory of the ATMs. Moreover, one additional difficulty in our pricing subproblem is the existence of column dependent rows, which means that we are forced to dynamically generate columns and rows simultaneously. We implement our B&P algorithm on the SCIP framework, obtaining promising results for selected real instances in Santiago, Chile. n WD05 North Bldg 122B

n WD01 North Bldg 121A Machine Learning via a Modern Optimization Lens Sponsored: Optimization/Optimization under Uncertainty Sponsored Session Chair: Dimitris Bertsimas, Massachusetts Institute of Technology, Cambridge, MA, 02139, United States 1 - Optimal Clustering Trees Agni Orfanoudaki, MIT, 77 Massachusetts Avenue, Cambridge, MA, United States, Holly Mika Wiberg, Dimitris Bertsimas State-of-the-art clustering algorithms use heuristics to partition the feature vectors while providing little insight regarding the interpretability of each cluster. We present a new Optimal Clustering Trees algorithm that leverages mixed- integer optimization (MIO) techniques to generate interpretable and globally optimal clustering tree models. We demonstrate that our method achieves superior performance on both synthetic and real-world datasets and scales even when the number of observations is high. 2 - Optimal Survival Trees Tree-based models are increasingly popular due to their ability to identify complex relationships that are beyond the scope of parametric models. Survival tree methods adapt these models to allow for the analysis of censored outcomes, which often appear in medical data. We present a new Optimal Survival Trees algorithm that leverages mixed-integer optimization (MIO) and local search techniques to generate globally optimal survival tree models. We demonstrate that the OST algorithm improves on the accuracy of existing survival tree methods, particularly in large datasets. 3 - Missing Data Imputation for Clinical Covariates with Time Series Colin Pawlowski, Massachusetts Institute of Technology, Cambridge, MA, United States, Dimitris Bertsimas, Agni Orfanoudaki, Ying Zhuo Missing data is a common problem in healthcare applications where researchers use EMR, claims data, and results of observational studies to apply analytics methods. We propose a family of optimization-based methods for imputation of data sets consisting of clinical covariates of patients observed over time. We derive first-order methods that find high quality solutions in minutes for data sets with 10,000s of patients and 100s of clinical covariates. We demonstrate that our method med.impute outperforms state-of-the-art methods in imputation accuracy and out-of-sample performance on downstream tasks on healthcare data sets with real and synthetic missing patterns. 4 - Optimal Classification Trees with Hyperplanes are as Powerful as Classification Neural Networks Matthew Sobiesk, Massachusetts Institute of Technology, Dimitris Bertsimas, Rahul Mazumder We investigate the modeling power of neural networks in comparison with optimal classification trees with hyperplanes (OCT-Hs). We prove that a variety of neural networks can be transformed to decision trees with hyperplanes, showing that OCT-Hs are at least as powerful as neural networks. Conversely, we show that a given classification OCT-H can be transformed to a classification neural network with the perceptron activation function, showing that these neural networks are at least as powerful as OCT-Hs, that is, OCT-Hs and these neural networks are equivalent in terms of modeling power. n WD04 North Bldg 122A Algorithms for MIP Applications Sponsored: Optimization/Integer and Discrete Optimization Sponsored Session Chair: Ayse Aslan, University of Groningen, Groningen, 9747 AE, Netherlands 1 - Energy Optimization of a Plug in Electric Vehicle Along a Fixed Path Emma Gibson, Massachusetts Institute of Technology, Dimitris Bertsimas, Jack W. Dunn, Agni Orfanoudaki

Bilgenur Guru, Middle East Technical University, Industrial Engineering. No: 326. Cankaya, Ankara, 06800, Turkey, Mustafa Kemal Tural, Arsham Atashi Khoei

Given an origin-destination pair and a fixed path between them, we consider the problem of determining the speed of a plug-in electric vehicle on each road segment along the path, the charging stations the vehicle will stop by, and how much to recharge at each stop so as to minimize the total amount energy consumption of the vehicle. We assume that there is a speedlimit on each road

496