event
PhD Defense by Ian Herszterg.
Primary tabs
Thesis Title: Efficient Algorithms for Solving MultiObjective Optimization and LargeScale Transportation Problems
Advisor:
Dr. Martin Savelsbergh, School of Industrial and Systems Engineering, Georgia Tech
Committee members:
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
Passcode: 7146
Abstract:
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 realworld 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 realworld largescale 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 tradeoffs in solution quality of assigning more or less priority to certain objectives.
Multiobjective 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 nondominated frontier) of pure integer linear programs with two and three objectives. The situation is quite different for multiobjective 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 multiobjective mixed integer programs and solving largescale 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 epsilonTabu 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 highquality 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 speedup factor of up to 18x (using 20 threads) compared to the modest speedup 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 reallife urban sameday 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 realestate 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 nontrivial integer programming model for solving the problem and, to be able to solve realworld 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 realworld 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 origindestination 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 nosplit multicommodity 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 depthfirst search manner with a prespecified 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 worstcase 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.
Groups
Status

Workflow Status:
Published 
Created By:
Tatianna Richardson 
Created:
07/08/2020 
Modified By:
Tatianna Richardson 
Modified:
07/08/2020
Categories
Keywords
Target Audience