Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd W. Easton / The possibility of becoming a millionaire attracts over 200,000 daily fantasy sports (DFS) contest entries each Sunday of the NFL season. Millions of people play fantasy sports and the companies sponsoring daily fantasy sports are worth billions of dollars. This thesis develops optimization models for daily fantasy sports with an emphasis on tiered contests. A tiered contest has many different payout values, including the highly sought after million-dollar prize. The primary contribution of this thesis is the first model to optimize the expected payout of a tiered DFS contest. The stochastic integer program, MMIP, takes into account the possibility that selected athletes will earn a distribution of fantasy points, rather than a single predetermined value. The players are assumed to have a normal distribution and thus the team’s fantasy points is a normal distribution. The standard deviation of the team’s performance is approximated through a piecewise linear function, and the probabilities of earning cumulative payouts are calculated. MMIP solves quickly and easily fits the majority of daily fantasy sports contests. Additionally, daily fantasy sports have landed in a tense political climate due to contestants hopes of winning the million-dollar prize. Through two studies that compare the performance of randomly selected fantasy teams with teams chosen by strategy, this thesis conclusively determines that daily fantasy sports are not games of chance and should not be considered gambling. Besides creating the first optimization model for DFS tiered contests, this thesis also provides methods and techniques that can be applied to other stochastic integer programs. It is the author’s hope that this thesis not only opens the door for clever ways of modeling, but also inspires sports fans and teams to think more analytically about player selection.

We consider a scheduling problem where each job requires multiple classes of resources, which we refer to as the multiple resource constrained scheduling problem(MRCSP). Potential applications include team scheduling problems that arise in service industries such as consulting and operating room scheduling. We focus on two general cases of the problem. The first case considers uncertainty of processing times, due dates, and resource availabilities consumption, which we denote as the stochastic MRCSP with uncertain parameters (SMRCSP-U). The second case considers uncertainty in the number of jobs to schedule, which arises in consulting and defense contracting when companies bid on future contracts but may or may not win the bid. We call this problem the stochastic MRCSP with job bidding (SMRCSP-JB).We first provide formulations of each problem under the framework of two-stage stochastic programming with recourse. We then develop solution methodologies for both problems. For the SMRCSP-U, we develop an exact solution method based on the L-shaped method for problems with a moderate number of scenarios. Several algorithmic enhancements are added to improve efficiency. Then, we embed the L-shaped method within a sampling-based solution method for problems with a large number of scenarios. We modify a sequential sampling procedure to allowfor approximate solution of integer programs and prove desired properties. The sampling-based method is applicable to two-stage stochastic integer programs with integer first-stage variables. Finally, we compare the solution methodologies on a set of test problems.For SMRCSP-JB, we utilize the disjunctive decomposition (D2 ) algorithm for stochastic integer programs with mixed-binary subproblems. We develop several enhancements to the D2 algorithm. First, we explore the use of a cut generation problem restricted to a subspace of the variables, which yields significant computational savings. Then, we examine generating alternative disjunctive cuts based on the generalized upper bound (GUB) constraints that appear in the second-stage of the SMRCSP-JB. We establish convergence of all D2 variants and present computational results on a set of instances of SMRCSP-JB.

Governments in many counties are taking measures to promote electric vehicles. An important strategy is to build enough charging infrastructures so as to alleviate drivers’ range anxieties. To help the governments make plans about the public charging network, we propose a multi-stage stochastic integer programming model to determine the locations and capacities of charging facilities over finite planning horizons. We use the logit choice model to estimate drivers’ random choices towards different charging stations nearby. The objective of the model is to minimize the expected total cost of installing and operating the charging facilities. Two simple algorithms are designed to solve this model, an approximation algorithm and a heuristic algorithm. A branch-and-price algorithm is also designed for this model, and some implementation details and improvement methods are explained. We do some numerical experiments to test the efficiency of these algorithms. Each algorithm has advantages over the CPLEX MIP solver in terms of solution time or solution quality. A case study of Oakville is presented to demonstrate the process of designing an electric vehicle public charging network using this model in Canada. / Thesis / Master of Science (MSc)

In this dissertation we focus on two main topics. Under the first topic, we develop a new framework for stochastic network interdiction problem to address ambiguity in the defender risk preferences. The second topic is dedicated to computational studies of two-stage stochastic integer programs. More specifically, we consider two cases. First, we develop some solution methods for two-stage stochastic integer programs with continuous recourse; second, we study some computational strategies for two-stage stochastic integer programs with integer recourse. We study a class of stochastic network interdiction problems where the defender has incomplete (ambiguous) preferences. Specifically, we focus on the shortest path network interdiction modeled as a Stackelberg game, where the defender (leader) makes an interdiction decision first, then the attacker (follower) selects a shortest path after the observation of random arc costs and interdiction effects in the network. We take a decision-analytic perspective in addressing probabilistic risk over network parameters, assuming that the defender's risk preferences over exogenously given probabilities can be summarized by the expected utility theory. Although the exact form of the utility function is ambiguous to the defender, we assume that a set of historical data on some pairwise comparisons made by the defender is available, which can be used to restrict the shape of the utility function. We use two different approaches to tackle this problem. The first approach conducts utility estimation and optimization separately, by first finding the best fit for a piecewise linear concave utility function according to the available data, and then optimizing the expected utility. The second approach integrates utility estimation and optimization, by modeling the utility ambiguity under a robust optimization framework following \cite{armbruster2015decision} and \cite{Hu}. We conduct extensive computational experiments to evaluate the performances of these approaches on the stochastic shortest path network interdiction problem. In third chapter, we propose partition-based decomposition algorithms for solving two-stage stochastic integer program with continuous recourse. The partition-based decomposition method enhance the classical decomposition methods (such as Benders decomposition) by utilizing the inexact cuts (coarse cuts) induced by a scenario partition. Coarse cut generation can be much less expensive than the standard Benders cuts, when the partition size is relatively small compared to the total number of scenarios. We conduct an extensive computational study to illustrate the advantage of the proposed partition-based decomposition algorithms compared with the state-of-the-art approaches. In chapter four, we concentrate on computational methods for two-stage stochastic integer program with integer recourse. We consider the partition-based relaxation framework integrated with a scenario decomposition algorithm in order to develop strategies which provide a better lower bound on the optimal objective value, within a tight time limit.

As energy demands increase and energy resources change, the traditional energy system has been upgraded and reconstructed for human society development and sustainability. Considerable studies have been conducted in energy expansion planning and electricity generation operations by mainly considering the integration of traditional fossil fuel generation with renewable generation. Because the energy market is full of uncertainty, we realize that these uncertainties have continuously challenged market design and operations, even a national energy policy. In fact, only a few considerations were given to the optimization of energy expansion and generation taking into account the variability and uncertainty of energy supply and demand in energy markets. This usually causes an energy system unreliable to cope with unexpected changes, such as a surge in fuel price, a sudden drop of demand, or a large renewable supply fluctuation. Thus, for an overall energy system, optimizing a long-term expansion planning and market operation in a stochastic environment are crucial to improve the system's reliability and robustness. As little consideration was paid to imposing risk measure on the power management system, this dissertation discusses applying risk-constrained stochastic programming to improve the efficiency, reliability and economics of energy expansion and electric power generation, respectively. Considering the supply-demand uncertainties affecting the energy system stability, three different optimization strategies are proposed to enhance the overall reliability and sustainability of an energy system. The first strategy is to optimize the regional energy expansion planning which focuses on capacity expansion of natural gas system, power generation system and renewable energy system, in addition to transmission network. With strong support of NG and electric facilities, the second strategy provides an optimal day-ahead scheduling for electric power generation system incorporating with non-generation resources, i.e. demand response and energy storage. Because of risk aversion, this generation scheduling enables a power system qualified with higher reliability and promotes non-generation resources in smart grid. To take advantage of power generation sources, the third strategy strengthens the change of the traditional energy reserve requirements to risk constraints but ensuring the same level of systems reliability In this way we can maximize the use of existing resources to accommodate internal or/and external changes in a power system. All problems are formulated by stochastic mixed integer programming, particularly considering the uncertainties from fuel price, renewable energy output and electricity demand over time. Taking the benefit of models structure, new decomposition strategies are proposed to decompose the stochastic unit commitment problems which are then solved by an enhanced Benders Decomposition algorithm. Compared to the classic Benders Decomposition, this proposed solution approach is able to increase convergence speed and thus reduce 25% of computation times on the same cases.