UC Berkeley

This dissertation studies analytical and computational aspects of two types of problems in applied operations research. In the first part of the dissertation, we consider the reliable facility location models in which facilities are subject to unexpected failures. We propose a compact mixed integer programming formulation that is polynomial in size. To compute optimal facility locations that balance the trade-off between normal operation and failure costs, we develop two exact algorithms: one is based on Lagrangian Relaxation, and the other is a hybrid of neighborhood search and cutting plane procedures. To obtain more managerial insights, we further investigate a Continuum Approximation (CA) model that predicts the total system cost without details about facility locations and customer assignments. The CA model is a valuable tool for sensitivity analysis, as well as a fast heuristic for large problem instances.

The second part of the dissertation is dedicated to theoretical and applied mechanism design, which consists of two chapters. In the first chapter, we study a problem of allocating limited capacity of a queueing system to serve several segments of customers, who differ in their willingness to pay and their sensitivity to delays, both of which are their private information. We show that probabilistic admission control, randomized priority rule, and strategic idleness can emerge as optimal solutions in a revenue maximizing mechanism.

In the second chapter of part two, we revisit the optimal auction design problem and propose a robust formulation based on an uncertainty set that characterizes the conservativeness of the bidders' beliefs, with two special cases being the Bayesian and Ex post formulations. Using the network approach, we identify the necessary and sufficient conditions under which the expected revenues achieved by different formulations are identical. Furthermore, we show that in a multiple-object auction, the auctioneer's expected revenue may strictly decrease as the bidders' beliefs become more uncertain.