Column generation for a UAV assignment problem with precedence constraints

We apply column generation with branch-and-price optimization to a multi-target, multi-task assignment problem, with precedence constraints. Column generation transforms the nonlinear program with separable costs and constraints into a linear program. This reformulation divides the original problem into a number of smaller problems, where one of these smaller problems accounts for the coupling constraints between agents and must be known by every agent. All other divisions consider local constraints affecting only one agent; these smaller problems are known by only one corresponding agent. Because of this reformulation, the assignment problem can be solved in a distributed manner. A theorem is proven which details the central analytical result of the paper, allowing a nonlinear program to be reformulated as a linear program. Simulation results for a multi-target, single-task assignment problem, as well as a multi-target, multi-task assignment problem with precedence constraints are presented. Published 2011. This article is a US Government work and is in the public domain in the USA.