Navy personnel planning and the optimal partition

One could argue that the Navy's most important resource is its personnel, and as such, workforce planning is a crucial task. We investigate a new model and solution technique that is designed to aid in optimizing the process of assigning sailors to jobs. This procedure attempts to achieve an increased level of sailor satisfaction by providing a list of possible jobs from which a sailor may choose. We show that the optimal partition provided by an interior-point algorithm is particularly useful when designing the job lists. This follows because a strictly complementary solution to the linear programming relaxation observes all possible optimal solutions to the original binary problem. The techniques developed rely on a continuous parametric analysis, and we show that the parameterization provides meaningful information about the structure of the optimal assignments.