Lagrangian relaxation guided problem space search heuristics for generalized assignment problems |
| |
Authors: | V Jeet E Kutanoglu |
| |
Institution: | Operations Research and Industrial Engineering Program, The University of Texas at Austin, Austin, TX 78712-0292, USA |
| |
Abstract: | We develop and test a heuristic based on Lagrangian relaxation and problem space search to solve the generalized assignment problem (GAP). The heuristic combines the iterative search capability of subgradient optimization used to solve the Lagrangian relaxation of the GAP formulation and the perturbation scheme of problem space search to obtain high-quality solutions to the GAP. We test the heuristic using different upper bound generation routines developed within the overall mechanism. Using the existing problem data sets of various levels of difficulty and sizes, including the challenging largest instances, we observe that the heuristic with a specific version of the upper bound routine works well on most of the benchmark instances known and provides high-quality solutions quickly. An advantage of the approach is its generic nature, simplicity, and implementation flexibility. |
| |
Keywords: | Assignment Generalized assignment problem Heuristics Problem space search Lagrangian relaxation |
本文献已被 ScienceDirect 等数据库收录! |
|