2015 Informs Annual Meeting

WA19

INFORMS Philadelphia – 2015

WA18 18-Franklin 8, Marriott Optimization Combinatorial I Contributed Session

4 - An Effective Approach to the Determination of Proper Equilibrium Chuangyin Dang, Professor, City University of Hong Kong, Dept. of SEEM, 83 Tat Chee Avenue, Kowloon, Hong Kong - PRC, mecdang@cityu.edu.hk, Yin Chen As a powerful refinement of Nash equilibrium, proper equilibrium plays an important role in the development of game theory. This paper aims to develop an effective smooth path-following method for computing proper equilibria. By appropriately incorporating barrier terms into payoff functions, we construct a smooth path to a proper equilibrium through closely approximating some Nash equilibrium of a perturbed game. Extensive numerical results further confirm the effectiveness of the method. WA17 17-Franklin 7, Marriott Network Analysis II Sponsor: Optimization/Network Optimization Sponsored Session Chair: Bahar Cavdar, Middle East Technical University, Ankara, Turkey, bcavdar@metu.edu.tr 1 - A Network-Based Approach to Bushfire Fuel Management Dmytro Matsypura, The University of Sydney, Bushfires represent a real and continuing problem that can have a major impact on people, wildlife and the environment. One way to reduce the severity of their effect is through fuel management. We propose a general methodology to address the problem of optimal resource allocation for bushfire fuel management subject to landscape connectivity and stochastic fuel regeneration. 2 - Empty Repositioning under Demand Uncertainty in Large-scale Transportation Networks Ilke Bakir, PhD Student, Georgia Institute of Technology, H. Milton Stewart School, 765 Ferst Dr NW, Atlanta, GA, 30332- 0205, United States of America, ilkebakir@gatech.edu, Alan Erera, Martin Savelsbergh We consider a transportation network where loaded demand quantities are uncertain, and only estimates are known. We introduce different methods of solving the repositioning problem on relatively sparse networks to satisfy as much demand as possible, using loaded demand estimates. We first experiment with various sharing group policies (hub/spoke structures for empty repositioning), and then introduce a robust optimization approach to further improve demand satisfaction. 3 - A Robust Framework for Event Prediction in Partially Unobserved Networks Aaron Schecter, Northwestern University, 2240 Campus Drive, 1-459, Evanston, IL, 60208, United States of America, aaronschecter2016@u.northwestern.edu, Noshir Contractor Longitudinal social network analysis is typically framed as a series of decisions by rational actors. However, individuals only have access to partial information about the whole network. As a result, behaviors are functions of both observed local ties as well as perceived second order relationships. We propose a statistical model for the prediction of dyadic link events under this assumption of network uncertainty; our technique draws from robust optimization and simulation principles. 4 - A Tabu Search with Time-based Preprocessing for Vehicle Routing Problem with Time Windows Bahar Cavdar, Middle East Technical University, Ankara, Turkey, bcavdar@metu.edu.tr, Joel Sokol Recent applications of Vehicle Routing Problem (VRP) such as online grocery shopping require finding solutions in a short time with little knowledge of the instance in advance. Current solution methods put more emphasis on the solution quality rather than the computation time. In this talk, we present a new heuristic for VRP with time windows. We combine a tabu search approach with a preprocessing of the instance using arc-based waiting time information to speed up the computation. Rm 478 Merewether Building H04, Sydney, Australia, dmytro.matsypura@sydney.edu.au, Oleg Prokopyev

Chair: Burcin Cakir Erdener, Dr., Baskent University, Eskisehir Yolu 20 km. Baglica Kampusu, Muhendislik Fak. Etimesgut, Ankara, 06800, Turkey, burcincakir55@gmail.com 1 - Dynamic-programming-based Inequalities for the Multi- dimensional Unbounded Knapsack Problem Xueqi He, University of Florida, 3800 SW 34th St. Apt. P138, Gainesville, FL, 32608, United States of America, xueqihe@gmail.com We present a new branch-and-cut approach for solving the multi-dimensional unbounded knapsack problem, where valid inequalities are generated for an integer programming formulation based on intermediate solutions of an equivalent dynamic programming formulation. These inequalities tighten the initial LP relaxation, and therefore improve the computational efficiency. 2 - An Exact Algorithm for Biobjective Mixed Integer Linear Programming Problems Gazi Bilal Yildiz, Res. Assist., Erciyes University, Engineering Faculty, Industrial Engineering, Kayseri, 38039, Turkey, bilalyildiz@erciyes.edu.tr, Banu Soylu In this study, we develop an algorithm to generate all Pareto line segments of BOMILPs. Our algorithm starts with the solution of an individual objective function and then sequentially generates all line segments of the Pareto frontier. At each iteration of the algorithm, one line segment of the Pareto frontier is detected. If there is no new Pareto line segment available, the algorithm ends. We provide a numerical example and present the performance of the algorithm over several test problems. 3 - Virtual Mixed Integer Nonlinear Programming Model for Integrated Electricity Distribution System Burcin Cakir Erdener, Dr., Baskent University, Eskisehir Yolu 20 km. Baglica Kampusu, Muhendislik Fak. Etimesgut, Ankara, 06800, Turkey, burcincakir55@gmail.com, Berna Dengiz, Zulal Gungor, Imdat Kara An electricity network design problem with distributed generation, which is called the Integrated Electricity Distribution System (IEDS) design problem is considered. The design procedure aims at the minimization of total system design cost while ensuring the optimum location and routing decisions for several system elements. To solve IEDS,a mixed-integer nonlinear-programming model is proposed. A new network transformation approach called virtual node duplicating is introduced within the model. WA19 19-Franklin 9, Marriott Computational Optimization for Applied Problems II Sponsor: Computing Society Sponsored Session Chair: Hans Mittelmann, Arizona State University, Box 871804, Tempe, United States of America, mittelmann@asu.edu 1 - Scip-jack -A Solver for the Steiner Tree Problem and Variants with Parallelization Extensions Stephen Maher, Zuse Institute Berlin, Takustr. 7, Berlin, BE, 14195, Germany, maher@zib.de, Gerald Gamrath, Thorsten Koch, Daniel Rehfeldt, Yuji Shinano The Steiner tree problem in graphs (STP) arises in practical applications as one of many variants. A relationship exists between the different STP variants, suggesting the potential for a generic solver. However, problem specific solutions approaches are commonly observed. SCIP-Jack is a general purpose solver to solve both the STP and many of its variants. Transformations are employed that permit STPs to be solved using a MIP-framework. The result is a massively parallel general STP solver. 2 - Compact MIP Formulation of the Selective Delivery and Pickup Problem Yuanyuan Dong, Southern Methodist University, 3101 Dyer Street, Dallas, TX, 75205, United States of America, ydong@smu.edu, Eli Olinick We present a compact MIP for the selective delivery and pickup problem with the objective of maximizing profit by accepting unscheduled deliveries during the time-limited trip. The MIP is inspired by a novel formulation of multicommodity flow that significantly reduces the size of the constraint matrix and the LP upper bound compared to a model based on the classical approach. This in turn leads to faster solution times when using commercial MIP codes, as we demonstrate in an empirical study.

379