Exact methods for solving linear and nonlinear max-min problems

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