Track: Doctoral Dissertation Research Presentation Competition

Abstract

In this research we aim to use robust optimization concepts and techniques in problems that arise in geographic resource allocation and also to use geometric partitioning techniques in robust optimization. A lot of problems in geographic resource allocation deal with uncertainty just like many other domains. Some of them like k-centers problem are naturally defined in a minimax essence and some others can be treated under uncertainty where we seek robust solutions. Most of the geographic resource allocation problems can be settled in one or more of the  categories like; location problems, segmentation (partitioning) problems, assignment problems, routing problems, and backbone network design problems. In all such problems there are parameters that can be unknown in practice. It is normal to define an uncertainty set for the unknown parameter based on some crude knowledge about unknown parameter and then treat the uncertainty like deterministic variability of the values of the parameter and solve the problem as the parameter is another variable in a higher dimension.

For such problems in geographic resource allocation, we take a robust approach to tackle the uncertainty. Depending on the problem and also geometry of the uncertainty set, the robust optimization model can be tractable or difficult to solve. We deal with both cases in this research where we combine elements from computational geometry, geometric probability theory, vector space optimization, and topology, to either solve the problem to optimality or develop fast algorithms to settle with an approximation solution.

In this dissertation we also present a divide and conquer type of approach using geometric partitioning to solve robust optimization problems. In a generic robust optimization problem if the uncertainty set is an infinite set, which is the case in most practical situations, then we will have an infinite/semi-infinite dimensional optimization problem since the model will have infinite number of constraints. We describe the draw backs of the current approaches to solving such problems and their inability to obtain reasonable solutions for some special but common and practical cases, like clustered data, and then we show that using our approach these problems can be easily solved in a more efficient way even for those special cases.