Parallel decomposition: A critical look

Summary form only given. Constraint optimization exists in many natural-computation applications, including neural and evolutionary computations. A key observation on the constraints of many of these application problems is that they are highly structured and involve variables with strong spatial or temporal locality. Based on this observation, large-scale problems in these applications can be partitioned by their constraints into a small number of much simpler subproblems. Because each subproblem has only a fraction of the original constraints, it is a significant relaxation of the original problem and has a dramatically lower complexity. As a result, many problems that cannot be solved before can now be solved easily. In this talk, we present the application of this approach in solving nonlinear optimization and automated planning problems. Based on a partition-and-resolve strategy, we evaluate penalty-based techniques for resolving violated global constraints. We further examine the limitations on using penalties to guide the evaluation of the partitioned constraints in planning problems. We argue that a top-down state-space approach is better and demonstrate its effectiveness on nonlinear constrained optimization and automated planning benchmarks.