Full metadata
Title
Exact Optimization Models and Algorithms for Large-scale Location and Interdiction Problems with Underlying Network Structure
Description
Networks are a versatile modeling tool for the cyber and physical infrastructure that characterize society. They can be used to describe system spatiotemporal dynamics, including distribution of commodities, movement of agents, and data transmission. This flexibility has resulted in the widespread use of network optimization techniques for decision-making in telecommunications, transportation, commerce, among other systems. However, realistic network problems are typically large-scale and require the use of integer variables to incorporate design or logical system constraints. This makes such problems hard to solve and precludes their wide applicability in the solution of applied problems. This dissertation studies four large-scale optimization problems with underlying network structure in different domain applications, including wireless sensor networks, wastewater monitoring, and scheduling. The problems of interest are formulated using mixed-integer optimization formulations. The proposed solution approaches in this dissertation include branch-and-cut and heuristic algorithms, which are enhanced with network-based valid inequalities and network reduction techniques. The first chapter studies a relay node placement problem in wireless sensor networks, with and without the presence of transmission obstacles in the deployment region. The proposed integer linear programming approach leverages the underlying network structure to produce valid inequalities and network reduction heuristics, which are incorporated in the branch-and-bound exploration. The solution approach outperforms the equivalent nonlinear model and solves instances with up to 1000 sensors within reasonable time. The second chapter studies the continuous version of the maximum capacity (widest) path interdiction problem and introduces the first known polynomial time algorithm to solve the problem using a combination of binary search and the discrete version of the Newton’s method. The third chapter explores the service agent transport interdiction problem in autonomous vehicle systems, where an agent schedules service tasks in the presence of an adversary. This chapter proposes a single stage branch-and-cut algorithm to solve the problem, along with several enhancement techniques to improve scalability. The last chapter studies the optimal placement of sensors in a wastewater network to minimize the maximum coverage (load) of placed sensors. This chapter proposes a branch-and-cut algorithm enhanced with network reduction techniques and strengthening constraints.
Date Created
2023
Contributors
- Mitra, Ankan (Author)
- Sefair, Jorge A (Thesis advisor)
- Mirchandani, Pitu (Committee member)
- Grubesic, Anthony (Committee member)
- Byeon, Geunyeong (Committee member)
- Arizona State University (Publisher)
Topical Subject
Resource Type
Extent
244 pages
Language
eng
Copyright Statement
In Copyright
Primary Member of
Peer-reviewed
No
Open Access
No
Handle
https://hdl.handle.net/2286/R.2.N.187307
Level of coding
minimal
Cataloging Standards
Note
Partial requirement for: Ph.D., Arizona State University, 2023
Field of study: Industrial Engineering
System Created
- 2023-06-06 07:14:07
System Modified
- 2023-06-06 07:14:16
- 1 year 5 months ago
Additional Formats