Essays on Applied Optimization Models

This dissertation studies several different optimization problems, and consists of five chapters. In Chapter 1, we consider a multiperiod binary Knapsack problem, along with several extensions. We propose fully polynomial time approximation schemes to these problems where applicable. We also prove the performance guarantee of some greedy algorithms, and propose parameterized approximation algorithms for some extensions. In Chapter 2, we propose several models to aggregate the distributed energy resources, where the aggregator can be profit-seeking or regulated. We design the two-part pricing mechanism for the aggregator to achieve full market efficiency. In Chapter 3, we analyze the sample complexity of decentralized Q-learning algorithms for stochastic games, in both the tabular case and the case with linear function approximation. In Chapter 4, we design a power purchase agreement (PPA), where a firm signs a long term contract with a renewable energy generator. The contract specifies a one-time transfer payment by the firm to the renewable energy generator, as an investment to build new renewable energy facilities. The firm then owns all the generation from these facilities for an extended period of time. We formulate the firm's decision on when to sign the PPA as an optimal stopping problem, and analyze the firm's optimal policies. Chapter 5 is motivated by an application in freight forwarding, where we formulate the freight forwarder's decisions on the assignment of shipments to containers as an integer program, which turns out to be a combination of the bin packing problem and the generalized assignment problem. We propose several heuristics for this problem and run numerical experiments on their performances.