PhD Defense by Ian Herszterg.
Thesis Title: Efficient Algorithms for Solving Multi-Objective Optimization and Large-Scale Transportation Problems
Dr. Martin Savelsbergh, School of Industrial and Systems Engineering, Georgia Tech
Dr. Natashia Boland, School of Industrial and Systems Engineering, Georgia Tech
Dr. Alan Erera, School of Industrial and Systems Engineering, Georgia Tech
Dr. Alejandro Toriello, School of Industrial and Systems Engineering, Georgia Tech
Dr. Mauricio Resende, Amazon
Date and Time: 7 - 9 pm ET, Tuesday July 14, 2020
Meeting URL: https://bluejeans.com/230702930/7146
Meeting ID: 230 702 930
The study of transportation problems has given rise to major developments in the fields of Applied Mathematics, Operations Research, and Industrial Engineering. However, the size of real-world instances often poses challenges for standard optimization algorithms and, thus, to the tractability of these problems. This calls for computationally efficient heuristics that can produce high quality solutions in a short period of time. Another layer of complexity in most real-world large-scale transportation problems is that planners have to take into account conflicting objectives when making decisions, most notably the minimization of transportation costs and the maximization of service quality. Often, the multiple objectives are converted into a single objective by linearly combining the objectives, which may not necessarily produce the desired solution. Approaches that produce Pareto optimal solutions are preferred, but are more involved and computationally intensive. With the set of Pareto solutions at hand, planners can make better decisions by analyzing the trade-offs in solution quality of assigning more or less priority to certain objectives.
Multi-objective integer linear programming problems have been studied for many decades in the field of Operations Research. There exist highly effective algorithms for generating the Pareto frontier (also known as the non-dominated frontier) of pure integer linear programs with two and three objectives. The situation is quite different for multi-objective mixed integer linear programs. Only a few computationally effective algorithms exist for biobjective mixed integer programs (BOMIPs) -- none for triobjective mixed integer linear programs -- and these have been proposed only relatively recently.
In this thesis, we address the two challenges highlighted above: solving multi-objective mixed integer programs and solving large-scale transportation problems. In Chapter 2, present a novel fast and robust algorithm for solving biobjective mixed integer programs. The algorithm extends and merges ideas from two existing methods: the epsilon-Tabu Method and the Boxed Line Method. The result is a fast and, importantly, robust algorithm for generating the non dominated frontier (NDF) of a BOMIP; it is robust in the sense that it works well across a wide range of instances with different characteristics. We demonstrate its efficacy in an extensive computational study. We also show that it is capable of producing a high-quality approximation of the NDF in a fraction of the time required to produce the complete NDF. Finally, we propose different parallelization techniques for the Boxed Line Method that achieve a significant speed-up factor of up to 18x (using 20 threads) compared to the modest speed-up factor of 1.06x obtained when we allow the commercial solver to use all available threads to solve the optimization models in parallel.
In Chapter 3, we study a new service network design problem encounter in a real-life urban same-day delivery system, in which the number of vehicles that can simultaneously load or unload at a hub is limited (hubs in densely populated metropolitan areas tend to be small due to high real-estate costs). Because of the presence of both time constraints for the commodities and capacity constraints at the hubs, it is no longer guaranteed that a feasible solution exists. We propose a non-trivial integer programming model for solving the problem and, to be able to solve real-world instances, we design and implement two heuristics: (1) a metaheuristic, and (2) a hybrid matheuristic, which takes advantage of the strengths of the metaheuristic and from an IP based heuristic approach. The efficacy of the heuristics is demonstrated on a number of real-world instances.
Finally, in Chapter 4, we study a novel incremental network design problem motivated by the expansion of hub capacities in package express service networks. We are given an existing and a target service network design, defined by a set of nodes, arcs, and origin-destination demands (commodities), and we seek to find a transition from the existing service network to the target service network, where the capacity of a subset of arcs has been increased. In each period, the capacity of a single arc can be increased and the cost in a period is given by the solution to a no-split multi-commodity flow problem. Our objective is to find a sequence of arc capacity expansions such that the total cost during the transition is minimized. We propose an integer programming model for solving the problem, as well as a set of greedy heuristics and an exact algorithm that explores the partial sequences of expansions in a depth-first search manner with a pre-specified order, where, for each partial sequence, we compute: (1) the cost associated with the partial sequence, and (2) upper and lower bounds on the remaining costs of the transition sequence, used to curtail the enumeration of all possible sequences. We provide worst-case analyses for the proposed greedy heuristics and compare the efficiency of the algorithms with traditional branch and bound methods used in commercial solvers on a set of artificial instances.