| Recent developments in the area of stochastic programming have resulted in considerable success in optimal decision making under uncertainty. However, much of the work in this area has been restricted to linear models, which are often inadequate in dealing with the combinatorial nature of decisions in many strategic planning problems. Consequently, researchers have proposed stochastic integer programming formulations. Owing to the non-convexities associated with the value function of integer programs, this class of problems is extremely difficult to solve. This thesis is concerned with the development, analysis, and implementation of exact and heuristic algorithms for stochastic integer programs with application to strategic planning under uncertainty.; In the first part of this thesis, we address a general class of two-stage stochastic integer programs with discrete distributions. Various stochastic location and resource allocation problems can be formulated in this manner. We exploit the structure of the value function of the second stage problem to develop a novel global optimization algorithm. The proposed scheme departs from those in the current literature in that it avoids explicit enumeration of the search space while guaranteeing finite termination.; The second part of this thesis addresses a class of multi-period, multi-facility capacity expansion problems. We first prove that the problem is NP-hard. Subsequently, we develop heuristic strategies for the deterministic and stochastic versions of the problem and prove, via probabilistic analyses, that these heuristics are asymptotically optimal as the number of planning periods increase. Applications addressing manufacturing technology selection and capacity expansion of chemical processing networks are presented.; In the final part of this thesis, we address a class of stochastic programs with discrete first stage decisions and decision-dependent uncertainties. These problems are formulated as 0–1 hyperbolic programs for which we use the theory of convex extensions to develop a reformulation scheme and an exact solution strategy. The proposed methods are used in a case study for locating restaurant franchises. |
