A cutting-plane method for Mixed-Logical Semidefinite Programs with an application to multi-vehicle robust path planning

The usual approach to dealing with Mixed Logical Semidefinite Programs (MLSDPs) is through the “Big-M” or the convex hull reformulation. The Big-M approach is appealing for its ease of modeling, but it leads to weak convex relaxations when used in a Branch & Bound framework. The convex hull reformulation, on the other hand, introduces a significant number of auxiliary variables and constraints and is only applicable if the feasible region consists of several disjunctive bounded polyhedra. This paper aims to circumvent these shortcomings by leveraging on Combinatorial Benders Cuts due to Codato & Fischetti and by constructing linear cuts based on a Farkas Lemma for Semidefinite Programming (SDP) within a Cutting-Plane framework. We employ the resulting Cutting-Plane algorithm in a Robust Model Predictive Control (RMPC) test application for multi-vehicle robust path planning with obstacle and inter-vehicle collision avoidance, taking into consideration exogenous (eg external wind gusts) and endogenous (eg internal noise in the system gain) uncertainty. We formulate this problem as an MLSDP model using minimax approaches by Löfberg and by El Ghaoui et al. and Big-M formulations due to Richards & How.