A network model to maximize Navy personnel readiness and its solution

The problem of optimally (re)allocating Navy personnel to combat units is compounded by several considerations: availability of trained personnel, staffing of positions by occupation groups or ranks, and maintaining an acceptable level of readiness. In this paper the authors model this problem as a nonlinear nondifferentiable optimization problem. A reformulation of the nonlinear optimization problem as a network flow problem is then developed. The formulation results in a network flow problem with side constraints. An additional, nonnetwork, variable measures the readiness level. This new formulation permits the use of network optimization tools in order to solve effectively very large problems. The authors then develop two numerical methods for solving this problem. One method is based on a heuristic that solves (approximately) the nondifferentiable problem. The second method is based on a Linear-Quadratic Penalty algorithm, and its exploits the embedded network structure by placing the side constraints into the objective function. The resulting nonlinear network program is solved using a simplicial decomposition of the network constraint set. Numerical results indicate the viability of this approach on problems with up to 36000 arcs and 17000 nodes with 3700 side constraints.