The primary focus of this dissertation is on solution methods for stochastic integer programs (SIP). We investigate large-scale mixed-integer programs arising from two-stage SIPs and present several techniques to improve existing decomposition algorithms for solving them. Our main goal is to improve linear programming relaxations, which can lead to significant reductions in the time to solve these problems to optimality.

We first study the problem of server scheduling in multiclass service systems under uncertainty in the customer arrival volumes. A common practice is to conduct the staffing and shift scheduling steps sequentially. We propose a two-stage SIP model that integrates these two decisions, which can yield similar quality-of-service with lower scheduling costs. As the standard Benders decomposition algorithm fails, we introduce a technique for using mixed-integer rounding to improve the Benders cuts, which is applicable to any SIP with integer first-stage variables. Numerical examples illustrate the computational efficiency of the proposed approach and the benefit of solving the integrated model.

Next, we investigate two frameworks to use integrality constraints to obtain improved cuts within Benders decomposition:​ (i) cut-and-project, where integrality constraints are used to derive cuts in the extended variable space, and Benders cuts are used to project the resulting improved relaxation, and (ii) project-and-cut, where integrality constraints are used to derive cuts directly in the Benders reformulation. For the case of split cuts, we demonstrate that although these approaches yield equivalent relaxations when considering a single split disjunction, cut-and-project yields stronger relaxations when using multiple split disjunctions. Computational results demonstrate that the difference can be very large, and the cut-and-project can significantly improve the performance of Benders decomposition.

Finally, we study extended formulations of linear relaxations of mixed-integer sets. We question whether there is a strongest possible extended formulation with respect to subsequent strengthening by lattice-free cuts. We give an explicit construction of one such extended formulation for general mixed-integer programs. For 0-1 mixed-integer programs with n integer and k continuous variables, we give an extended formulation with 2n + k − 1 variables whose split closure is integral. Computational results show the strength of cutting planes derived from extended formulations.