Crashing a maximum-weight complementary basis

The authors consider the problem of finding a maximum-weight complementary basis of an m×2m matrix. The problem arises naturally, for example, when a complementary set of columns is proposed as an initial basis for a ‘warm start’ of Lemke’s algorithm, but the set of columns is rank-deficient. The author show that the problem is a special case of the problem of finding a maximum-weight common base of two matroids. Furthermore, they show how to efficiently implement an algorithm for the general problem in the present context. Finally, the authors give computational results demonstrating the practicality of the present algorithm in a typical application.