Reliability constrained integer programming models with applications to facility location

This dissertation is concerned with the design of reliable systems. Two general research subjects are addressed: (1) modeling the optimal design of real world systems from a reliability perspective, and, as a result, producing integer optimization models, and (2) demonstrating a general polyhedral approach as a solution method for a particular type of integer programming (IP) model.;Specifically, one well recognized real world problem--the emergency service vehicle location problem--is studied extensively as an interesting application that reflects the above two themes of this dissertation.;In regard to the first research subject, all problems we study are formulated as linear 0-1 IP models with reliability constraints and cost minimization objective function. Since computing reliabilities for complex systems is in general a difficult problem, we base the constraints on bounds or approximations for the reliability measures in order to solve the models in a reasonable amount of computing time. To exploit the linear integer optimization techniques, we must formulate linear constraints. Linear IP optimization is thus the other focus of this dissertation.;A substantial portion of this dissertation is devoted to developing a cutting plane based polyhedral approach to solve the IP model established from the emergency service vehicle location problem. Cutting planes, or valid inequalities, for the convex hull of the integer feasible points are identified and added to "strengthen" the IP formulation, and thus to improve the linear programming (LP) relaxation bound to be used in branch-and-bound procedures. Analytical results in this regard are developed.;Our computational experience shows that the IP formulation strengthening techniques are very effective in improving the efficiency of branch-and-bound procedures. These techniques can thus be generalized as solution strategies for other similar IP problems. To evaluate the usefulness of the reliability model established for the location problem, we conducted sensitivity studies. The results show that the model is capable of providing effective solutions to different problem scenarios.;In addition, this dissertation develops a general approach for constructing reliability constrained IP models for the general binary coherent systems. A stochastic personnel assignment problem is used to illustrate this approach.