Dynamic Ideas LLC — Department of Defense SBIR Phase I: Exact formulations of weapon-to-threat assignment problems have long been identified as bi

Description

Exact formulations of weapon-to-threat assignment problems have long been identified as binary polynomial optimization problems which are theoretically difficult (NP-hard), thus previous research for implementation in the area has focused on heuristic solution methods or methods which compromise full formulation with limits on assignment. The introduction of sensor pairing further complicates formulation and solution. However, we explain an approach in this proposal to transform problems of this type into what are known as binary second-order cone problems. While still in the same theoretical computational complexity class, such problems have proven to be practically efficiently solvable by commercial optimization engines such as CPLEX and Gurobi. The algorithm we propose to develop and test in Phase I implements our proposed modeling approach on a detailed formulation of the simultaneous asset pairing and engagement scheduling problem thus fully integrating optimization of the exact problem.