Approximation Algorithms for Stochastic Integer Programming
A Factor 1/2 Approximation Algorithm for Two-Stage Stochastic Matching Problems by Nan Kong and Andrew J. Schaefer (to appear in European Journal of Operational Research).
Abstract: Two-stage stochastic mixed-integer programs are extremely difficult to solve. We consider two-stage stochastic mixed-integer programs with nonnegative first-stage objective functions and expected recourse functions and give a factor 1/2 approximation algorithm. We extend this algorithm to a class of multi-stage stochastic mixed-integer programs. We introduce two-stage stochastic matching, and demonstrate that this problem is NP-complete and that the bound given by the algorithm is tight. Computational results on some instances indicate that the approximation algorithm appears to be effective.
Stochastic Network Design
A Stochastic Intra-Ring Synchronous Optical Network Design Problem by J. Cole Smith, Andrew J. Schaefer and Joyce Yen (in Networks, volume 44, number 1, pp. 12-26).
Honorable Mention, Best Paper Award, INFORMS Junior Faculty Interest Group (JFIG), 2004.
Abstract: We develop a stochastic programming approach to solving an intra-ring Synchronous Optical Network (SONET) design problem. This research differs from pioneering SONET design studies in two fundamental ways. First, while traditional approaches to solving this problem assume that all data are deterministic, we observe that for practical planning situations, network demand levels are stochastic. Second, while most models disallow demand shortages and focus only on the minimization of capital Add-Drop Multiplexer (ADM) equipment expenditure, our model minimizes a mix of ADM installations and expected penalties arising from the failure to satisfy some or all of the actual telecommunication demand. We propose an L-shaped algorithm to solve this design problem, and demonstrate how a nonlinear reformulation of the problem may improve the strength of the generated optimality cuts. We next enhance the ba-sic algorithm by implementing powerful lower and upper bounding techniques via an assortment of modeling, valid inequality, and heuristic strategies. Our computational results conclusively demonstrate the efficacy of our proposed algorithm as opposed to standard L-shaped and extensive form approaches to solving the problem.
Locating Hybrid Fuel Cell-Turbine Power Generation Units Under Uncertainty by Laura A. Schaefer and Andrew J. Schaefer (in Annals of Operational Research, volume 132, pp. 301-332).
Abstract: Hybrid gas turbine-solid oxide fuel cell power generation has the potential to create a positive economic and environmental impact. Annually, the U.S. spends over $235 billion on electricity, and electric utilities emit 550 million metric tons of carbon. The integration of distributed hybrid generation can reduce these emissions and costs through increased efficiencies. In this paper, a model is presented that minimizes the costs of distributed hybrid generation while optimally locating the units within the existing electric infrastructure. The model utilizes data from hybrid generation modules, and includes uncertainty in customer demand, weather, and fuel costs.
SPAR: Stochastic Programming with Adversarial Recourse by Matthew D. Bailey, Steven M. Shechter and Andrew J. Schaefer (in Operations Research Letters, volume 172, pp. 740-746).
Abstract: We consider a general adversarial stochastic optimization model that is an extension of stochastic interdiction models. Our model involves the design of a system that an adversary may subsequently attempt to destroy or degrade. The designer faces uncertain parameters that are revealed after a design is selected. In addition, the adversary’s decision environment is also stochastic and dynamic. We introduce SPAR, which utilizes mixed-integer programming for the design decision and a Markov decision process (MDP) for the modeling of our adversarial phase. By exploiting the mathematical structure of the MDP formulation, we are able to show that SPAR converges in a finite number of iterations. We illustrate its computational effectiveness in reducing the number of adversarial problems computed and discuss the use of methods to solve the resulting adversarial MDPs efficiently.
Two-Stage Integer Programs with Stochastic Right-Hand Sides: A Superadditive Dual Approach by Nan Kong, Andrew J. Schaefer and Brady Hunsaker (to appear in Mathematical Programming Series B).
Abstract: We consider two-stage pure integer programs with discretely distributed stochastic right-hand sides. We present an equivalent superadditive dual formulation that uses the value functions in both stages. We give two algorithms for finding the value functions. To solve the reformulation after obtaining the value functions, we develop a global branch-and-bound approach and a level-set approach to find an optimal tender. We show that our method can solve randomly generated instances that are several orders of magnitude larger than those found in the literature.
Column Generation within the L-shaped Method for Stochastic Linear Programs by Mehmet C. Demirci, Brady Hunsaker, Andrew J. Schaefer and Jay Rosenberger (under review)
Abstract: Stochastic programming is a technique for optimization in the presence of uncertainty which typically leads to very large problem sizes. We develop a method for incorporating column generation within the L-shaped method for solving two-stage stochastic linear programs. This method adds feasibility and optimality cuts generated from the second-stage subproblems based on the current columns in the master problem of the L-shaped method. It also generates columns for the master problem with respect to the first-stage constraints as well as existing feasibility and optimality cuts. We present different algorithmic strategies and discuss convergence issues. To demonstrate the computational performances of the algorithmic approaches, we explore a two-stage stochastic version of the cutting stock problem.
Totally Unimodular Stochastic Programs by Nan Kong, Andrew J. Schaefer and Shabbir Ahmed (under review)
Abstract: We consider totally unimodular stochastic programs, that is, stochastic programs whose extensive-form constraint matrix is totally unimodular. We generalize the notion of total unimodularity to apply to sets of matrices and provide properties of such sets. Using this notion, we give several sufficient conditions for stochastic programs to be totally unimodular, and provide necessary conditions for specific classes of problems. When solving such problems using the L-shaped method it is not clear whether the integrality restrictions should be imposed on the master problem. Such restrictions will make each master problem more difficult to solve. On the other hand, solving the linear relaxation of the master typically means sending fractional (and unlikely optimal) solutions to the subproblems, perhaps leading to more iterations. Our computational results investigate this trade-off and provide insight into which strategy is preferable under a variety of circumstances.