Scandinavian Working Papers in Business Administration
Discussion Papers,
Norwegian School of Economics, Department of Business and Management Science
No 2014/1: A New Semi-Lagrangean Relaxation for the K-Cardinality Assignment Problem
Ivan Belik () and Kurt Jörnsten ()
Additional contact information
Ivan Belik: Dept. of Business and Management Science, Norwegian School of Economics, Postal: NHH , Department of Business and Management Science, Helleveien 30, N-5045 Bergen, Norway
Kurt Jörnsten: Dept. of Business and Management Science, Norwegian School of Economics, Postal: NHH , Department of Business and Management Science, Helleveien 30, N-5045 Bergen, Norway
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
24 pages, January 15, 2014
Full text files
227006
- Norwegian School of Economics, Department of Business and Management Science
- Ordering Working Papers
- Home page for this series
Questions (including download problems) about the papers in this series should be directed to Stein Fossen ()
Report other problems with accessing this service to Sune Karlsson ().
RePEc:hhs:nhhfms:2014_001This page generated on 2024-11-12 04:36:03.