Dynamic Ideas LLC — Department of Defense SBIR Phase II: 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 (Non-deterministic polynomial-time-hard or 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. Using advanced analytics, we developed a detailed formulation of the simultaneous asset pairing and engagement scheduling problem thus fully integrating optimization of the exact problem. Moreover, we introduced an innovative linearization approach that exploits the nature of the problem data and manages to solve the problem efficiently using commercial optimization engines. We are currently extending our analysis using robust optimization methods to address the stated problem under uncertainty. These robust optimization methods allow us to optimize over uncertainty in the problem data and derive solutions that are less sensitive to errors in point estimates of parameters. In Phase II we will enhance our formulation to capture more complex dynamics between different engagements, make certain that the robust optimization extends to this more realistic version as well, and finally we will further refine our algorithms to ensure real-time implementations in realistic stressed environments. Approved for Public Release 14-MDA-7739 (18 March 14).