Investigation of k-rationality & cutting plane methods in sequentially connected 2D assignment problems

Abstract

Integer linear optimization problems are generally difficult to solve efficiently due to the discrete nature of their solution spaces. A common approach to address these difficulties is to relax the integrality constraints, solve a continuous optimization problem, and utilize different methods to recover near-optimal integer solutions’. This thesis explores the usage of such approaches in the context of the Time-extended Generalised Optimal Sub-Pattern Assignment (TGOSPA) metric—a performance measure for the evaluation of multiple object tracking algorithms. Specifically, this can be seen as examining a binary sequentially connected 2D assignment problem where the binary requirement has been relaxed. Two primary methods for recovering binary optimal solutions are considered; one based on the concept of k-rationality and the other on using different cutting plane methods derived from fractional Gomory cuts. The results suggests that k-rationality is numerically unsuitable for this specific problem, and that the Gomory-based cutting methods lack performance consistency. Finally, an outline of several different directions for future research, based on the observations made in this thesis, is presented.