Repulsive Assignment Problem

M. Gaudioso (), L. Moccia () and M. F. Monaco ()
Additional contact information
M. Gaudioso: Università della Calabria
L. Moccia: Consiglio Nazionale delle Ricerche
M. F. Monaco: Università della Calabria

Journal of Optimization Theory and Applications, 2010, vol. 144, issue 2, No 4, 255-273

Abstract: Abstract Standard assignment is the problem of obtaining a matching between two sets of respectively persons and positions so that each person is assigned exactly one position and each position receives exactly one person, while a linear decision maker utility function is maximized. We introduce a variant of the problem where the persons individual utilities are taken into account in a way that a feasible solution must satisfy not only the standard assignment constraints, but also an equilibrium constraint of the complementarity type, which we call repulsive. The equilibrium constraint can be, in turn, transformed into a typically large set of linear constraints. Our problem is NP-hard and it is a special case of the assignment problem with side constraints. We study an exact penalty function approach which motivates a heuristic algorithm. We provide computational experiments that show the usefulness of a heuristic mechanism inspired by the exact approach. The heuristics outperforms a state-of-the-art integer linear programming solver.

Keywords: Generalized assignment problems; Quadratic assignment problems; Memetic algorithms; Equilibrium constraints (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-009-9601-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:joptap:v:144:y:2010:i:2:d:10.1007_s10957-009-9601-9

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-009-9601-9

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().