Solving strike force asset allocation problems: An application of 0/1 multidimensional knapsack problems with multiple-choice constraints

The strike-force asset-allocation problem consists of grouping strike force assets into packages and assigning these packages to targets and defensive assets in a way that maximizes the strike force potential. Integer programming formulations are developed, semi-real and random problems are built up, various approaches of a tabu search heuristic are developed, and computational results via both the CPLEX MIP Solver and the tabu search heuristic are presented. The use of tight oscillation near the feasibility boundary in the tabu search heuristic helps to obtain good solutions very quickly. The merits of using surrogate-constraint information versus using a Lagrange multiplier approach are demonstrated. Intensifying the neighborhood of good solutions via various trial solution approaches helps to obtain solutions of high quality.