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

Ivan Belik and Kurt Jörnsten

No 2014/1, Discussion Papers from Norwegian School of Economics, Department of Business and Management Science

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.

Keywords: K-cardinality assignment; Lagrangean Relaxation; Mathematical Programming (search for similar items in EconPapers)
JEL-codes: C00 C60 C61 (search for similar items in EconPapers)
Pages: 24 pages
Date: 2014-01-15
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://hdl.handle.net/11250/227006 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hhs:nhhfms:2014_001

Access Statistics for this paper

More papers in Discussion Papers from Norwegian School of Economics, Department of Business and Management Science NHH, Department of Business and Management Science, Helleveien 30, N-5045 Bergen, Norway. Contact information at EDIRC.
Bibliographic data for series maintained by Stein Fossen ().