|dc.description.abstract||This thesis focuses on developing exact solution methods for mixed-integer linear and nonlinear maxmin problems.
The first essay proposes a tri-level min-max-min optimization problem (pM-FLPI) to design a resilient
food banking network. The lower two levels together constitute a facility interdiction problem (FIP) that
helps find the most critical subset of food banks. We propose alternate single-level reformulations for FIP.
Using “Map the meal gap” data and the GIS-based location data, we perform a vulnerability analysis on the
existing Feeding America network. Furthermore, we propose a cutting plane approach, using Super-Valid
Inequalities (SVI), to efficiently solve pM-FLPI. We demonstrate the advantages of the proposed food
banking network for Feeding America obtained using pM-FLPI. Finally, utilizing the National Family
Health Survey, 2016 and the GIS data, we propose the design of a resilient network for the Indian Food
Banking Network (IFBN).
In the second essay, we develop an exact method to solve nonlinear max-min problems with a convex
objective function. The method is applied to the facility interdiction problem with congestion. Our proposed solution method iteratively generates an upper bound using an inner approximation of the convex
objective function, and a lower bound from an overall feasible solution. The feasible solution is further
used to generate better approximation in the subsequent iteration to progress towards the global optimal
solution. The proposed algorithm solves the problem very efficiently, and significantly outperforms a
more common second-order conic programming reformulation-based approach, which only handles specific convex functions.
In the third essay, we extend our proposed approach for nonlinear max-min problems to handle discrete
variables at both levels. Such problems commonly arise in nonlinear knapsack interdiction and single
allocation convex capacitated facility interdiction. The presence of the discrete variables at the lowerlevel problem enormously increases the computational difficulty of an already challenging problem. The
solution method builds on the inner-approximation-based approach proposed in the second essay, with
an additional step to approximate the convex hull of the feasible solutions of lower-level problem. Our
algorithm is able to solve large scale instances of both the problems efficiently||en_US