A New Semi-Lagrangean Relaxation for the K-Cardinality Assignment Problem

Abstract

Recently Beltrán-Royo, Vial & Alonso-Ayuso (2012) presented a semi-Lagrangean relaxation for the classical p-median location problem and for the incapacitated facility location problem. The results, obtained using the semi-Lagrangean relaxation approach, were quite impressive. In this paper we use a semi-Lagrangean relaxation to obtain an efficient solution method for the kcardinality assignment problem. The method has only one semi-Lagrangean multiplier that can only take on a limited number of values, making the search for the optimal multiplier easy. Since the semi-Lagrangean relaxation closes the duality gap, this leads to an extremely reliable and easily implementable method for finding k-cardinality assignments in large-scale cases. The method is computationally tested on the examples commonly used in the literature.