A New Semi-Lagrangean Relaxation for the K-Cardinality Assignment Problem
Working paper
Åpne
Permanent lenke
http://hdl.handle.net/11250/227006Utgivelsesdato
2014-01Metadata
Vis full innførselSamlinger
- Discussion papers (FOR) [566]
Sammendrag
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.