Chance-constrained missile-procurement and deployment models for naval surface warfare

Abstract

We model the problem of minimum-cost procurement and allocation of anti-ship cruise missiles to naval combat ships as a two-period chance-constrained program with recourse. Discrete scenarios in two periods define "demands" for missiles (i.e., targets and number of missiles required to kill those targets), which must be met with acceptable probabilities. After the first combat period, ships may replenish their inventories from a depot, if the depot's inventory suffices. A force commander assigns targets to ships based on missile load-outs and target demands. The deterministic-equivalent integer program solves too slowly for practical use. We propose a specialized decomposition algorithm, implemented in MATLAB, which solves the two-period model via a series of single-period problems. The algorithm yields optimal solutions for a wide range of missile-allocation directives, and usually near-optimal solutions otherwise. We exploit the fact that each single-period problem is a probabilistic integer program, whose solution must be a p-efficient point (PEP) of that period's demand distribution. Our algorithm uses PEP-enumeration techniques developed by Beraldi and Ruszczyski, and a specialized algorithm from Kress, Penn and Polukarov. The algorithm solves real-world problem instances in a few minutes or less.