Assignment with en route training of Navy personnel

Each year over 200000 Navy enlisted personnel are assigned new jobs at a cost of over 250 million dollars in moving expenses. The task of selecting assignments is complicated by the fact that an individual can be sent to a technical school (which has a limited capacity) to obtain additional training which makes him eligible for additional jobs. The optimal assignment of Navy personnel with en route training is addressed via an assignment problem with specially structured side constraints. This article presents a new algorithm to solve the integer network problem which is based on resource-directive decomposition in conjunction with Lagrangian relaxation. The new solution procedure is very fast compared to alternate methods.