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

View/ Open
Date
2014-01Metadata
Show full item recordCollections
- Discussion papers (FOR) [556]
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.