Preprocessing rules for integer programming solutions to the generalised assignment problem
- PDF / 275,851 Bytes
- 9 Pages / 595 x 842 pts (A4) Page_size
- 96 Downloads / 163 Views
#2001 Operational Research Society Ltd. All rights reserved. 0160-5682/01 $15.00 www.palgrave.com/jors
Preprocessing rules for integer programming solutions to the generalised assignment problem M-T Kong* and N Shah Imperial College of Science, Technology and Medicine, London, UK Several preprocessing rules to reduce integer programming problem size are proposed and examined for the generalised assignment problem. The rules make use of the linear programming relaxation and ranking on the basis of a combined resource=cost metric. Computational experiments with commercial branch and bound solvers have been performed using publicly available problem data from the OR library. Results are promising as the preprocessed problem solves to within 1% of the full problem with signi®cantly less CPU time for most of the test problems examined. Keywords: assignment; optimisation; heuristics; preprocessing rules
Introduction The Generalised Assignment Problem The Generalised Assignment Problem is an NP-hard combinatorial optimisation problem1 which considers the minimum cost assignment of n tasks to m agents such that each task is only assigned to one agent subject to capacity constraints on the agents. The GAP problem has many applications including resource scheduling, assigning software development tasks to programmers, assigning jobs to computers in computer networks, and many others.2 Instances of GAP are characterised by size, by degree of capacitation of agents, and by degree of hardness in terms of correlation between cost of assignment and the resources consumed by a task. Literature review There exists a considerable body of literature on the Generalised Assignment Problem. Current exact algorithms for the Generalised Assignment Problem depend on forms of tree search. Most methods are effective only for problems that are reasonably sized and not too `hard'. Exact algorithms have been proposed by Ross and Soland,3 and also by Martello and Toth,4 whose methods utilise relaxations based on deleting the capacity constraints of the agents and=or the single job to agent constraint. Fisher, Jaikumar, and Van Wassenhove5 proposed a method based on Lagrangian relaxation with unidirectional multiplier update, which is improved upon by Guignard and
*Correspondence: M-T Kong, Centre for Process Systems Engineering, Imperial College of Science, Technology and Medicine, South Kensington, London SW7 2BY, UK. E-mail: [email protected]
Rosewein.6 Wilcox proposed a similar method using Lagrangian relaxation but with bidirectional multiplier update. These methods are comprehensively treated by Cattrysse and Van Wassenhove.2 More recently, column generation and brand-and-bound have been combined to solve the problem in a set partitioning formulation by Savelsbergh7 while Narciso and Lorena8 consider a combined Lagrangian=surrogate approach which showed improved computational performance for `large problems' compared to Lagrangian heuristics. Heuristics and approximation algorithms for the generalised assignment problem have been proposed
Data Loading...
