Please use this identifier to cite or link to this item: http://hdl.handle.net/10419/147623
Authors: 
Klose, Andreas
Drexl, Andreas
Year of Publication: 
2001
Series/Report no.: 
Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 545
Abstract: 
Assignment type problems consist in optimally assigning or allocating a given set of "activities" to a given set of "resources". Optimisation problems of the assignment type have numerous applications in production planning and logistics. A popular approach to solve such problems or to compute lower bounds on the optimal solution value (in case of a minimisation problem) is to employ column generation. By means of considering subsets of "activities" which can feasibly be assigned to a single resource, the problem is reformulated as some kind of set-partitioning problem. Column generation is then used in order to solve the linear relaxation of the reformulation. The lower bound obtainable from this approach may, however, be improved by partitioning the set of resources into subsets and by considering subsets of activities which can feasibly be assigned to subsets of resources. This paper outlines the application of this partitioning method to a number of important combinatorial optimisation problems of the assignment type.
Document Type: 
Working Paper

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.