Preprocessing rules for integer programming solutions to the generalised assignment problem

Abstract

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 significantly less CPU time for most of the test problems examined.

Keywords:

• assignment
• optimisation
• heuristics
• preprocessing rules