New Valid Inequalities in Branch-and-Cut-and-Price for Multi-Agent Path Finding

Abstract

BCP, a state-of-the-art algorithm for optimal Multi-agent Path Finding, uses the branch-and-cut-and-price framework to decompose the problem into (1) a master problem that selects a set of collision-free low-cost paths, (2) a pricing problem that adds lower-cost paths to the master problem, (3) separation problems that resolve various kinds of conflicts in the master problem, and (4) branching rules that split the nodes in the high-level branch-and-bound search tree. This paper focuses on the separation aspects of the decomposition by introducing five new classes of fractional conflicts and valid inequalities that remove these conflicts to tighten the linear programming relaxation in the master problem. Experimental results on 12820 instances across 16 maps indicate that including the five families of inequalities allows BCP to solve an additional 585 instances, optimize the same instances 41% faster, and solve 2068 more instances than CBSH-RM and 157 more than Lazy CBS.