In this thesis I focus on cutting planes for large Mixed Integer Programming (MIP) problems. More specifically, I focus on two independent cutting planes studies. The first of these deals with cutting planes for the Traveling Salesman Problem (TSP), and the second with cutting planes for general MIPs. In the first study I introduce a new class of cutting planes which I call the Generalized Domino Parity (GDP) inequalities. My main achievements with regard to these are: (1) I show that these are valid for the TSP and for the graphical TSP. (2) I show that they generalize most well-known TSP inequalities (including combs, domino-parity constraints, clique-trees, bipartitions, paths and stars). (3) I show that a sub-class of these (which contains all clique-tree inequalities w/ a fixed number of handles) can be separated in polynomial time, on planar graphs. My second study can be subdivided in two parts. In the first of these I study the Mixed Integer Knapsack Problem (MIKP) and develop a branch-and-bound based algorithm for solving it. The novelty of the approach is that it exploits the notion of "dominance" in order to effectively prune solutions in the branch-and-bound tree. In the second part, I develop a Mixed Integer Rounding (MIR) cut separation heuristic, and embed the MIKP solver in a column generation algorithm in order to assess the performance of said heuristic. The goal of this study is to understand why no other class of inequalities derived from single-row systems has been able to outperform the MIR. Computational results are presented.

With the rapidly growing need for long-term decision making in the presence of stochastic future events, it is important to devise novel mathematical optimization tools and develop computationally efficient solution approaches for solving them. Two-stage stochastic programming is one of the powerful modeling tools that allows probabilistic data parameters in mixed integer programming, a well-known tool for optimization modeling with deterministic input data. However, akin to the mixed integer programs, these stochastic models are theoretically intractable and computationally challenging to solve because of the presence of integer variables. This dissertation focuses on theory, algorithms and applications of two-stage stochastic mixed integer (non)linear programs and it has three-pronged plan. In the first direction, we study two-stage stochastic p-order conic mixed integer programs (TSS-CMIPs) with p-order conic terms in the second-stage objectives. We develop so called scenario-based (non)linear cuts which are added to the deterministic equivalent of TSS-CMIPs (a large-scale deterministic conic mixed integer program). We provide conditions under which these cuts are sufficient to relax the integrality restrictions on the second-stage integer variables without impacting the integrality of the optimal solution of the TSS-CMIP. We also introduce a multi-module capacitated stochastic facility location problem and TSS-CMIPs with structured CMIPs in the second stage to demonstrate the significance of the foregoing results for solving these problems. In the second direction, we propose risk-neutral and risk-averse two-stage stochastic mixed integer linear programs for load shed recovery with uncertain renewable generation and demand. The models are implemented using a scenario-based approach where the objective is to maximize load shed recovery in the bulk transmission network by switching transmission lines and performing other corrective actions (e.g. generator re-dispatch) after the topology is modified. Experiments highlight how the proposed approach can serve as an offline contingency analysis tool, and how this method aids self-healing by recovering more load shedding. In the third direction, we develop a dual decomposition approach for solving two-stage stochastic quadratically constrained quadratic mixed integer programs. We also create a new module for an open-source package DSP (Decomposition for Structured Programming) to solve this problem. We evaluate the effectiveness of this module and our approach by solving a stochastic quadratic facility location problem. / Doctor of Philosophy / With the rapidly growing need for long-term decision making in the presence of stochastic future events, it is important to devise novel mathematical optimization tools and develop computationally efficient solution approaches for solving them. Two-stage stochastic programming is one of the powerful modeling tools that allows two-stages of decision making where the first-stage strategic decisions (such as deciding the locations of facilities or topology of a power transmission network) are taken before the realization of uncertainty, and the second-stage operational decisions (such as transportation decisions between customers and facilities or power flow in the transmission network) are taken in response to the first-stage decision and a realization of the uncertain (demand) data. This modeling tool is gaining wide acceptance because of its applications in healthcare, power systems, wildfire planning, logistics, and chemical industries, among others. Though intriguing, two-stage stochastic programs are computationally challenging. Therefore, it is crucial to develop theoretical results and computationally efficient algorithms, so that these models for real-world applied problems can be solved in a realistic time frame. In this dissertation, we consider two-stage stochastic mixed integer (non)linear programs, provide theoretical and algorithmic results for them, and introduce their applications in logistics and power systems. First, we consider a two-stage stochastic mixed integer program with p-order conic terms in the objective that has applications in facility location problem, power system, portfolio optimization, and many more. We provide a so-called second-stage convexification technique which greatly reduces the computational time to solve a facility location problem, in comparison to solving it directly with a state-of-the-art solver, CPLEX, with its default settings. Second, we introduce risk-averse and risk-neutral two-stage stochastic models to deal with uncertainties in power systems, as well as the risk preference of decision makers. We leverage the inherent flexibility of the bulk transmission network through the systematic switching of transmission lines in/out of service while accounting for uncertainty in generation and demand during an emergency. We provide abundant computational experiments to quantify our proposed models, and justify how the proposed approach can serve as an offline contingency analysis tool. Third, we develop a new solution approach for two-stage stochastic mixed integer programs with quadratic terms in the objective function and constraints and implement it as a new module for an open-source package DSP We perform computational experiments on a stochastic quadratic facility location problem to evaluate the performance of this module.