Efficient Optimal and Approximate Algorithms in Optimization Under Uncertainty

Abstract

Some of the most important and challenging decisions must be made with incomplete information. This lack of information can refer to ignorance regarding events or conditions that have happened or events that have yet to occur. This lack of information can relate to what decisions are available as well as the consequences of these decisions. Optimization under uncertainty has applications in a wide range of settings including hiring (How good is the candidate? Will a better candidate arrive?), disaster relief (Where are people who need help? How long do rescue teams have before they are in a more critical condition?), and manufacturing (How much will we be able to manufacture? What orders should we accept?). These problems can be solved naively by reformulating the problem as a deterministic problem, but this can dramatically increase the size of the problem making the naive reformulation to be computationally expensive to solve. We aim to develop efficient algorithms to solve optimization problems under uncertainty and construct approximate algorithms that quickly approximate the solution in instances that are too large to solve exactly. In Chapter 2, we discuss a secretary problem with generalized decisions. The goal is to “rank” incoming items arriving in an uncertain order. Once an item arrives, it must be assigned a rank before the next item arrives, and this cannot be changed when new items arrive. We exploit the structure of the problem using exact dynamic programming to construct an algorithm that can be used to compute an exact solution. Additionally, we develop heuristics that can be used to construct an approximate solution in larger problems. In Chapter 3, we discuss a search and rescue drone problem. In this problem, we construct routes to maximize the number of people who are in need of rescue in the event of a natural disaster. After constructing a nonlinear mixed-integer program (MIP), we construct simplifying policies that allow us to solve it in real-time allowing for updates as new information is learned. In Chapter 4, we discuss a two-stage stochastic knapsack problem. In manufacturing settings, orders must be accepted or rejected before it is known how much resources will be available to fill those orders. We formalize this problem as a two-stage stochastic knapsack problem. We construct lower bounds based on feasible solutions and upper bounds based on the optimal solutions of a relaxation of the problem. We then use these bounds to construct optimal solutions that beat traditional solvers. We then develop algorithms that construct approximate solutions for larger instances that perform well compared to the optimal solutions.