We study the problem of routing jobs in multi-class multi-server queueing systems, where the service rate depends both on the job type and the server type. This queueing setting arises in different applications. For example, in transportation systems, a vehicle's travel time depends on the job's location (e.g., a fire incident's location) and the vehicle's location (e.g., a fire station). In call centers, an agent's service time depends on her skills and the call type that is routed to her.

Chapter I focuses on maximizing the service level of jobs defined as the probability that a job is served within an acceptable waiting time. Service level is an important performance measure for queueing systems. For example, emergency vehicle networks should make sure that the selected server (e.g., a fire engine) arrives at the requester's location within the specified acceptable waiting time. We employ a mathematical programming approach which is desirable since it can easily be embedded within larger planning problems such as determining the optimal location of vehicle hubs and finding the minimum number of vehicles for the desired coverage level. We show that the expected waiting time is convex with respect to its variables, namely, arrival rate and workload. For this reason, the expected waiting time objective is more common in the literature, even though in many applications it is the service level function which is more practical. The service level function, however, is non-convex and requires more advanced methods to solve for optimal or near-optimal solutions. We develop one such advanced method, the Fixed-ratio Shifting Envelopes (FSE) method. Our extensive numerical experiments indicate that FSE outperforms other benchmark algorithms as well as the global solver BARON. In Chapter I, we end our treatment of the subject with the static policy developed for this novel math programming formulation.

Chapter II seeks online (or, real-time) routing policies that answer two questions: (i) Upon a job arrival, to which server group should we assign that job? and (ii) When a server becomes free, which job should the server begin to serve? We point out that the optimal dynamic policy for minimizing the expected waiting time or maximizing the service level is not characterized in the literature. In Chapter II we focus on designing a dynamic policy for the widely-used measure of minimizing the expected waiting time. We develop a math program to model a static variant of our routing problem. Then, we use the solution from our math program to build novel dynamic policies. Our experiments show that one of our proposed overflow dynamic routing policies, which we call FSFOptXOverflowBlock, outperforms Fastest-Server-First, a well-known routing policy for such problems in practice and in the literature. To showcase our methodology, we apply our proposed policy to the problem of assigning fire incidents in Irvine, CA, to fire stations. Methodologically, one could extend this so-called dynamization technique to also construct dynamic policies for the service level maximization problem of Chapter I. We leave the details for future research.

Motivated by recent trends in online advertising, most of this dissertation is devoted to the introduction, modeling, and the design of efficient allocation techniques for a new form of online advertising contract, which we refer to as Reach and Frequency (R&F) contract.

In the first chapter, we consider a type of R&F contract which allows online advertisers to specify the number of unique individuals that should see their ad (reach), and the minimum number of times each individual should be exposed (frequency) for him/her to be counted as reached. We develop an optimization framework that provides minimal under-delivery and proper spread of each campaign over its targeted demographics. As well, we introduce a pattern-based delivery mechanism which allows us to integrate a variety of new features into a website's ad allocation optimization problem, e.g., allowing publishers to implement any desired pacing of ads over time at the user level or control the number of competing brands seen by each individual. Numerical tests, conducted on real industry data obtained from Yahoo, show that our solution algorithm produces high-quality solutions and has promising run-time and scalability. Several extensions of the model are presented, e.g., to account for multiple ad positions on the webpage, or randomness in the website visitors' arrival process.

In the second chapter, we consider different variants of R&F contracts in which the advertiser specifies frequency using a probability distribution that details what fraction of users should see the ad how many times. We propose two Markov chain models for serving ads, namely when frequencies are counted over a fixed timespan or on a rolling basis. We then investigate how each Markov chain performs in maintaining the desired frequency distribution of an online ad campaign. In each case, we characterize the feasibility criteria, and show that the publisher's impression assignment rule can be obtained very efficiently in linear time in the length of the frequency distribution specified by the advertiser.

In the final chapter, we present a new online competitive algorithm for delivering online guaranteed targeted display advertising which, under certain conditions, outperforms the best known algorithm of its type.

Since its inception, Benders Decomposition (BD) has been successfully applied to a wide range of large-scale mixed-integer (linear) problems that lie at the heart of operations research and supply chain management. The inherent capacity of BD for exploiting the structural properties of problems with complicating variables has made it one of the most prominent exact algorithms for solving large-scale optimization problems. Over the years, BD has grown in its ability to solve a wide range of challenging problems including variants of facility location problems, supply chain and network design problems, scheduling and routing problems, healthcare operations, machine learning, and variants of stochastic programming problems among several other applications. This dissertation is structured into three research papers. First, we introduce a general acceleration technique for BD by introducing deepest Benders cuts. As an application of BD on problems arising in the transportation and logistics sector, we introduce efficient and novel implementations of BD for variants of hub location problems. We further analyze effects of uncertainty in demand and revenues in hub location problems and propose novel modelling and solution methods based on robust and stochastic optimization techniques.

The key element of BD is the derivation of Benders cuts, which are often not unique. In the first chapter, we introduce a novel unifying Benders cut selection technique based on a geometric interpretation of cut ``depth'', produce deepest Benders cuts based on 1p-norms, and study their properties. Specifically, we show that deepest cuts resolve infeasibility through minimal deviation from the incumbent point, are relatively sparse, and may produce optimality cuts even when classical Benders would require a feasibility cut. Leveraging the duality between separation and projection, we develop a Guided Projections Algorithm for producing deepest cuts while exploiting the combinatorial structure or decomposablity of problem instances. We then propose a generalization of our Benders separation problem that brings several well-known cut selection strategies under one umbrella. In particular, by establishing its connection to our method, we provide systematic ways of selecting the normalization coefficients in the Minimal Infeasible Subsystems method.We also provide general implementation guidelines, which are useful beyond the scope of this study. Finally, in our tests on facility location problems, we show deepest cuts often reduce both runtime and number of Benders iterations, as compared to other cut selection strategies; and relative to classical Benders, use 1/3 the number of cuts and 1/2 the runtime. As an application of accelerating Benders decomposition, we model capacity allocation decisions within profit maximizing hub location problems to satisfy demand of commodities from different market segments. We present a strong deterministic formulation of the problem and describe two exact algorithms based on a Benders reformulation to solve large-size instances of the problem. We show that the subproblems can be broken into smaller and simpler problems in two phases. We prove that the first phase can be efficiently solved using a cutting-plane algorithm. To produce strong cuts, we cast the second phase as a multi-objective optimization problem. We show that non-dominated solutions to the second phase can be obtained by either a set of continuous maximum weighted matching problems, or by a series of continuous knapsack problems in a sequential manner. We further enhance the performance of the algorithms by integrating improved variable fixing techniques. We evaluate the efficiency and robustness of the algorithms through extensive computational experiments. Computational results show that large-scale instances with up to 500 nodes and three demand segments can be solved to optimality, and that the proposed algorithms generate cuts that provide significant speedups compared to using Pareto-optimal cuts. The proposed two-phase methodology for solving the Benders subproblem as well as the variable fixing and acceleration techniques can be used to solve other discrete location and network design problems. Finally, we extend the deterministic model by considering uncertainty associated with the demand to develop a two-stage stochastic program. To solve the stochastic version, we develop a Monte-Carlo simulation-based algorithm that integrates a sample average approximation scheme with the proposed Benders decomposition algorithms. We then extend the models by simultaneously incorporating two sources of uncertainty including stochastic demand and uncertain revenue. To incorporate uncertain revenues into the problem, we use robust optimization techniques and investigate two particular cases including interval uncertainty and discrete scenarios. We formulate robust-stochastic models with a max-min profit criterion and a min-max regret objective for the former and latter cases, respectively. We enhance the Benders decomposition algorithms coupled with sample average approximation scheme by novel acceleration techniques. We also conduct extensive computational experiments to analyze the effects of uncertainty under different settings and compare the quality of the solutions obtained from different modeling approaches under different parameter settings. Computational results demonstrate the efficiency of the proposed algorithms and justify the need for embedding both sources of uncertainty in decision making to provide robust solutions.

The censored demand estimation problem has been well studied over the past 20 years. Theseminal paper is Talluri and Van Ryzin 2004, which models demand as the product of an unobserved arrival rate and purchase probability, and uses Expectation Maximization (EM) for estimation. In this work, I apply their model to the case of a small hotel with a single product, and adapt the model to use a time-varying arrival rate. Modeling the arrival rate as a step function, the choice of where the steps fall is a crucial hyperparameter, so I propose a heuristic algorithm, the Step Variance Minimization Heuristic (SVMH), to specify the size and location of the steps in the arrival rate function. On both real and simulated hotel data, SVMH is superior in terms of both in-sample and out-of-sample mean squared error when compared to (a) a constant arrival rate and (b) evenly-spaced steps of the same num- ber. To improve the convergence time of EM, I introduce a variant algorithm, Regularized Expectation Maximization (REM), that uses 81% fewer iterations than EM, on average. I show that REM is a Generalized Expectation Maximization (GEM) algorithm, and thus has similar theoretical properties to EM. I also conducted multiple numerical studies that show that models estimated using REM perform similarly in-sample and out-of-sample to their EM counterparts, and produce nearly identical revenue curves. Thus, the convergence improvements offered by REM do not come at a cost to good parameter estimation.