Pricing the generalized assignment problem

Andreas Drexl and Kurt Jörnsten

No 627, Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel from Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre

Abstract: The generalized assignment problem (GAP) examines the maximum profit assignment of jobs to processors such that each job is assigned to precisely one processor subject to capacity restrictions on the processors. Due to the fact that the GAP is an NP-hard integer program dual prices are not readily available. In this paper we propose a family of linear programming models the optimal solution of which is integral "almost always". We provide a computational proof of this conjecture by an in-depth experimental study of 1500 instances generated according to the standard procedure adopted in literature. Summarizing this analysis we have linear prices for all but 17 of the whole bunch of instances and, hence, there exists a linear price function that supports the optimal assignment of jobs to processors.

Keywords: Generalized assignment problem; integer programming; duality; linear programming; pricing (search for similar items in EconPapers)
Date: 2007
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.econstor.eu/bitstream/10419/147680/1/manuskript_627.pdf (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:zbw:cauman:627

Access Statistics for this paper

More papers in Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel from Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre Contact information at EDIRC.
Bibliographic data for series maintained by ZBW - Leibniz Information Centre for Economics (econstor@zbw-workspace.eu).