On the variable-depth-search heuristic for the linear-cost generalized assignment problem

Bertrand M.T. Lin, Y. S. Huang, H. K. Yu

Research output: Contribution to journalArticlepeer-review


The classical assignment problem seeks to determine a mapping between a set of assignees and a set of assignments. The linear cost assignment problem (LCGAP), as a generalized model, incorporates the relative workloads between assignees and assignments. Although LCGAP is computationally intractable, it has been extensively studied because of its practical implications in many real world situations. Variable-depth-search heuristic (VDSH) method is one of the solution methods that have been developed to produce quality near-optimal solutions to LCGAP. The main structure of VDSH consists of two basic operations: reassign and swap. In this paper, we make further observations on this effective heuristic method through a series of computational experiments. The numerical results statistically evince that different combinations of these two operations will result in solutions of different quality levels. These findings are expected to have similar implications to search heuristics for other optimization problems.

Original languageEnglish
Pages (from-to)535-544
Number of pages10
JournalInternational Journal of Computer Mathematics
Issue number4
Publication statusPublished - 2001

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'On the variable-depth-search heuristic for the linear-cost generalized assignment problem'. Together they form a unique fingerprint.

Cite this