Informs Annual Meeting 2017

TE74

INFORMS Houston – 2017

4 - Interrelationship Between the Impending Major Energy Transitions and Pollutant Emissions

5 - Slim Branch and Price Method for Combinatorial Optimization Problems

Daniela Quiroga, Pontificia Universidad Catolica de Chile, Santiago, Chile, diquiroga@uc.cl, Enzo Sauma, David Pozo

Ahmed M. Marzouk, Southern Methodist University, Lyle School of Engineering, Southern Methodist University, Dallas, TX, 75275- 0123, United States, ambadr@email.tamu.edu, Erick Moreno-Centeno, Halit Uster The Slim Branch and Price (SBP) method is a new optimization method that can be described as a framework that borrows ideas from general branch-and-price and cutting plane frameworks. We describe a specific implementation of the SBP algorithm and illustrate its effectiveness in a generalized traveling salesperson problem known as the Hamiltonian p-Median Problem.

Energy sector is facing important transitions motivated by the strong incentives for encouraging renewable energy production and the adoption of energy efficiency measures. We study the interrelationship between the impending energy transitions over the coming decade and local and global pollutant emissions, in the context of the Chilean power system. In particular, we develop and analyze policy-relevant scenarios describing the energy transitions facing Chile over the coming decades and identify the key factors of the power sector contributing to pollutant emissions. We then identify some regulations in the Chilean power sector and study the general and distributional effects on emissions. 372A Optimization, Large Scale Contributed Session Chair: Ahmed Marzouk, Southern Methodist University, Dallas, TX, United States, amarzouk@smu.edu 1 - Solving Uncapacitated Facility Location and Network Design Problems with Disaggregagted Benders Decomposition Robin Pearce, University of Queensland, School of Mathematics and Physics, Mathematics Department, St Lucia, 4068, Australia, r.pearce2@uq.edu.au Numerous problems fall under the category of facility location and network design problems, most of which can be effectively solved using Benders decomposition. In this talk we list a number of these problems, present the general problem and show how to apply disaggregated Benders decomposition these problems. In particular, we look at potential improvements that can be applied to improve time to solution, such as Pareto-optimal analytically-derived Benders cuts or tighter feasibility cuts. We will conclude with computational results to demonstrate the effectiveness of this approach. 2 - Robust Optimization to One-way Electric Vehicles Sharing System Considering Uncertain Travel Time zihao jiao, Beijing Institute of Technology, Beijing, China, zihaobit@163.com As operators’ concern, the main problems of Electric vehicles sharing service such as charging demand and range anxiety, impact operation process and generate several secondary problems. Another unnoticeable aspect of operation is uncertainty, a general issue in engineering systems. We propose a robust model to handle with perturbed data, taking location and layout into consideration as well. Then we use a two-stages algorithm to solve the model. The results of case study show that uncertainty of travel time makes an unstable fleet size each depot, increasing optimal cost and worse cost management ability. Besides, we appraise environment benefits by evaluate the CO2 saving by EVs sharing. 3 - A New Lagrangian Relaxation for Multicommodity Capacitated Network Design Problem Mohammad Rahim Akhavan Kazemzadeh, Universite de Montreal (DIRO), 5775 ave Wilderton, Montreal, QC, H3S2V7, Canada, akhavanm@iro.umontreal.ca, Teodor Gabriel Crainic, Bernard Gendron The usual Lagrangian relaxations for multicommodity capacitated network design are the so-called shortest path and knapsack relaxations, which are obtained, respectively, by relaxing linking constraints and flow conservation equations. We present a new reformulation and Lagrangian relaxation for the problem. We show that the Lagrangian dual bound improves upon the so-called strong LP bound (known to be equal to the Lagrangian dual bounds of the shortest path and knapsack relaxations). 4 - The Constrained Covering Tour Problem Sanaz Goldani, PhD Student, North Carolina State University, 3610 Detrick Drive, Apt 321, Raleigh, NC, 27609, United States, sgoldan@ncsu.edu, Yahya Fathi The Constrained Covering Tour Problem (CCTP) is an integer programming (IP) problem that arises in the context of solving the Bi-objective Maximal-covering Minimal-tour Problem (BCTP) via the -constraint method. We introduce a family of valid inequalities and propose a branch-and-cut algorithm for solving this IP problem. We also present the results of a computational experiment to assess the effectiveness of this algorithm. We then employ this algorithm to obtain the non- dominated frontier of the corresponding bi-objective optimization problem. TE72

TE73

372B 4:35 - 5:20 Turner/ 5:20 - 6:05 DiDi Chuxing Invited: Vendor Tutorial Invited Session 1 - Analytics and Data Science at Turner

Helena Berube, Turner Broadcasting Systems Inc, Atlanta, GA, United States, Helena.berube@turner.com, J. Antonio Carbajal Analytics and Data Science plays a critical role at Turner. Our team is uniquely positioned to serve our clients with a focus on innovation, execution and nimble ability. Learn about some of the exciting work we’ve done that is transforming the media and content business. 2 - Didi Chuxing Technology Session

Wan Zhixi, Didi Chuxing, Beijing, China, wanzhixi@didichuxing.com, Adam Li

(Didi Chuxing is the world’s leading mobile transportation platform.) You are warmly invited to learn more about our business and research topics related to platform economics, operations management, transportation science and engineering. You will learn about various opportunities to work together with our internal research teams.

TE74

372C Parallel Algorithms in Optimization Sponsored: Computing Sponsored Session Chair: Oleg Shylo, University of Tennessee, Knoxville, TN, 37996, United States, oshylo@utk.edu 1 - Parallel Branch and Bound Algorithms for Rectangular Maximum Agreement Jonathan Eckstein, Rutgers University, 100 Rockafeller Road, Room 5145, Piscataway, NJ, 08854, United States, jeckstei@rci.rutgers.edu, Ai Kagawa Rectangular maximum agreement (RMA) in an NP-hard combinatorial problem arising as a subproblem in various machine learning contexts. We show how the problem arises and discuss its solution using the PEBBL parallel branch-and- bound framework. We discuss various possible branching strategies and the specialized data structures that facilitate them. We give parallel performance results on problem instances derived from real datasets, and may also discuss restricted versions on the problem intended to be easier to solve. 2 - A Flocking-based Approach for Distributed Stochastic Optimization Shi Pu, University of Florida, Gainesville, FL, United States, sp3dw@virginia.edu, Alfredo Garcia We consider a distributed asynchronous computing scheme for stochastic optimization with modest communication amongst processors. Specifically, we analyze a scheme with N > 1 independent threads implementing each a stochastic gradient algorithm. The threads are coupled via a perturbation of the gradient (with attractive and repulsive forces) in a similar manner to mathematical models of flocking found in nature. We show a flocking-like approach provides a noise reduction effect similar to that of a centralized algorithm. Moreover, when the overhead related to the time needed to gather N samples and synchronization is not negligible, the flocking implementation outperforms a centralized one.

437