Irreducible Infeasible Subsystem Decomposition for Probabilistically Constrained Stochastic Integer Programs

Date

2013-07-25

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

This dissertation explores methods for finding irreducible infeasible subsystems (IISs) of systems of inequalities with binary decision variables and for solving probabilistically constrained stochastic integer programs (SIP-C). Finding IISs for binary systems is useful in decomposition methods for SIP-C. SIP-C has many important applications including modeling of strategic decision-making problems in wildfire initial response planning.

New theoretical results and two new algorithms to find IISs for systems of inequalities with binary variables are developed. The first algorithm uses the new theory and the method of the alternative polyhedron within a branch-and-bound (BAB) approach. The second algorithm applies the new theory and the method of the alternative polyhedron to a system in which zero/one box constraints are appended. Decomposition schemes using IISs for binary systems can be used to solve SIP-C.

SIP-C is challenging to solve due to the generally non-convex feasible region. In addition, very weak lower (upper) bounds on the objective function are obtained from the linear programming (LP) relaxation of the deterministic equivalent problem (DEP) to SIP-C. This work develops a branch-and-cut (BAC) method based on IIS inequalities to solve SIP-C with random technology matrix and random righthand- side vector. Computational results show that the LP relaxation of the DEP to SIP-C can be strengthened by the IIS inequalities.

SIP-C modeling can be applied to wildfire initial response planning. A new methodology for wildfire initial response that includes a fire behavior simulation model, a wildfire risk model, and SIP-C is developed and tested. The new method- ology assumes a known standard response needed to contain a fire of given size. Likewise, this methodology is used to evaluate deployment decisions in terms of the number of firefighting resources positioned at each base, the expected number of escaped and contained fires, as well as the wildfire risk associated with fires not receiving a standard response. A study based on the Texas district 12 (TX12) that is one of the Texas A&M Forest Service (TFS) fire planning units in east Texas demonstrates the effectiveness of the new methodology towards making strategic deployment decisions for wildfire initial response planning.

Description

Citation