Dr. Eli Olinick from Southern Methodist University will present at the Seminar Monday February 12 at 1:15pm in Room 105 of Nedderman Hall. Dr. Olinick’s presentation title, abstract, and biographical sketch are below.
Title: Compact Multicommodity Flow Formulation with Applications to Vehicle Routing, Concurrent Flow, and Social Network Analysis
Author: Eli Olinick
Location: Nedderman Hall (NH) Room 105
Date: Monday, February 12
Time: 1:15pm – 2:15pm
Abstract: We present a compact mixed integer program (MIP) for the vehicle routing problem with optional pickup and delivery in which a freight carrier seeks to generate revenue from an empty delivery vehicle’s backhaul trip from its last scheduled delivery to its depot by allowing it to deviate from the least expensive (or fastest) route to accept delivery requests between intermediate points as allowed by its capacity and required return time. The MIP is inspired by a novel representation of multicommodity flow, the triples formulation, that significantly reduces the size of the constraint matrix and the linear programming upper bound on optimal profit compared to a formulation based on the classical node-arc representation. This in turn leads to faster solution times when using a state-of-the-art MIP solver. In an empirical study of both formulations, problem instances with ten potential pickup/dropoff locations (including the vehicle’s current location and its depot) were solved three to twelve times faster with our formulation while instances with 20 locations were solved 90 to 2,000 times faster. The largest instances in the study had 40 locations and 1,482 delivery requests; these instances could not be solved with the node-arc-based formulation, but were solved within an average of 90 minutes of CPU time using our compact formulation. We present a similar study applying the triples formulation to the notoriously difficulty maximum concurrent flow problem (MCFP), an optimization problem concerning the equitable use of resources in congested networks. In this study we found that the CPLEX linear programming solvers solved 89% of the MCFP instances in our computational study faster with the triples formulation than it did with the other two formulations, typically two to four times faster than the node-edge formulation when available computer memory allowed both to be solved. The triples formulation appears to be particularly well suited for problem instances defined on dense graphs; on average, CPLEX solved these types of problems in our study 10 times faster with the triples formulation. Finally, we propose a new clustering algorithm based on hierarchical maximum concurrent flow (HMCF) and its duality relation to the sequence of sparsest cuts, and discuss theoretical properties which make it more accurate and often more robust than many popular algorithms in the literature. We present a new measure of node centrality, determined from the HMCF, called flowthrough centrality, and empirical results comparing its improved stability relative to currently used centrality measurements employed in social network analysis when knowledge of the network topology is incomplete or in transition.
Biographical Sketch: Eli V. Olinick is an Associate Professor in the Department of Engineering Management, Information, and Systems at SMU’s Bobby B. Lyle School of Engineering. He completed his B.S. in Applied Mathematics (1989) at Brown University and earned his M.S. (1994) and Ph.D. (1999) in Industrial Engineering and Operations Research at the University of California at Berkeley. Professor Olinick’s research interests include applied optimization and network design problems. His research activities have been funded by multiple government and industry grants totaling over $1.6M, and he has published over 20 refereed research articles in prominent journals in operations research and network engineering. He is a past president of the INFORMS Technical Section on Telecommunications, the Dallas/Fort Worth INFORMS chapter, and an Associate Editor of Networks and Spatial Economics.
-Posted by Jay Rosenberger