Thesis Title: Decomposition Algorithms for Certain Integer Problems over Networks

Thesis Committee:

Dr. Nikolaos Sahinidis (advisor), School of Industrial and Systems Engineering, Georgia Institute of Technology

Dr. Santanu Dey (advisor), School of Industrial and Systems Engineering, Georgia Institute of Technology

Dr. Diego Cifuentes, School of Industrial and Systems Engineering, Georgia Institute of Technology

Dr. John-Paul Clarke, Cockrell School of Engineering, The University of Texas at Austin

Dr. Alejandro Toriello, School of Industrial and Systems Engineering, Georgia Institute of Technology

Date and Time: Thursday, July 20, 2023, 10:00am - 12:00pm EST

Meeting Link: https://gatech.zoom.us/j/2029701440?pwd=WC9wOUNvUHpBeHlpU1dVY2sydGQ5QT09

Join our Cloud HD Video Meeting

Zoom is the leader in modern enterprise video communications, with an easy, reliable cloud platform for video and audio conferencing, chat, and webinars across mobile, desktop, and room systems. Zoom Rooms is the original software-based conference room solution used around the world in board, conference, huddle, and training rooms, as well as executive offices and classrooms. Founded in 2011, Zoom helps businesses and organizations bring their teams together in a frictionless environment to get more done. Zoom is a publicly traded company headquartered in San Jose, CA.

gatech.zoom.us

Abstract:

Integer optimization stands as a fundamental and widely embraced tool in addressing many real-world problems. Among the abundant applications of integer optimization, numerous network-related problems arise and exhibit significant influence in many areas such as transportation, energy systems, and supply chains. The intricate nature of these problems often results in complicated large-scale formulations that are computationally expensive to solve directly. Instead, decomposition is a more computationally tractable means in many cases. In this thesis, we focus on a few integer problems over networks.

In Chapter 2, we investigate the airport flight-to-gate assignment problem, where the goal is to minimize the total delays by optimally assigning each scheduled flight to a compatible gate. We provide a column generation approach for solving this problem. We decompose the pricing problem such that each gate is the basis for an independent pricing problem to be solved and use a combination of an approximation algorithm based on the submodularity of the underlying set and dynamic programming algorithms to solve the independent pricing problems. We also design and employ a rolling horizon method and block decomposition algorithm to solve the large-sized instances. Finally, we perform extensive computational experiments to validate the performance of our approach.

In Chapter 3, we focus on the gas network design problem. Gas networks are used to transport natural gas, which is an important resource for both residential and industrial customers throughout the world. The gas network design problem is a challenging nonlinear and non-convex optimization problem. We propose a decomposition framework to solve this problem. In particular, we utilize a two-stage procedure that involves a convex reformulation of the original problem. We conduct experiments on a benchmark network to validate and analyze the performance of our framework.

In Chapter 4, we combine the water network design and operation problems. In general, the design problems consider pipe sizing and placements of pump stations, while the operation problems are multiple time period problems that account for temporal changes in supply and demand and consider the scheduling of the installed pump stations. We propose two methods to obtain good candidate primal solutions. One method is a similar decomposition framework that is used in Chapter 3 while the other method is based on a time decomposition. We conduct computational experiments on networks that closely resemble real-world networks.

In Chapter 5, we consider the resiliency of infrastructure networks. The infrastructure systems generally consist of multiple types of infrastructure facilities that are interdependent. In the event of natural disaster, some of the infrastructure nodes can be damaged and disabled creating failures and such failures can propagate to other facilities that depend on the disabled facilities creating a cascade of failures and eventually a potential system collapse. We propose a bilevel interdiction model to study this problem of cascading failures in an interdependent infrastructure network with a probabilistic dependency graph. We utilize a Benders type decomposition algorithm to solve the resulting formulation. Computational experiments are performed using synthetic networks to validate the performance of this algorithm.