An efficient procedure for finding best compromise solutions to the multi-objective assignment problem |
| |
Affiliation: | 1. Department of Radiology, Queen Mary Hospital, University of Hong Kong, Hong Kong;2. Department of Neurosurgery, Queen Elizabeth Hospital, Hong Kong;3. Department of Radiology and Imaging, Queen Elizabeth Hospital, Hong Kong;1. Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60-965 Poznan, Poland;2. Institute of Bioorganic Chemistry, Polish Academy of Sciences, Noskowskiego 12/14, 61-704 Poznan, Poland;1. 3S Consult GmbH, Karlsruhe, Germany;2. lrstea, Water Department, Bordeaux regional centre, Cestas F-33612, France;3. 3S Consult GmbH, Karlsruhe, Germany |
| |
Abstract: | In this paper, we consider the problem of determining a best compromise solution for the multi-objective assignment problem. Such a solution minimizes a scalarizing function, such as the weighted Tchebychev norm or reference point achievement functions. To solve this problem, we resort to a ranking (or k-best) algorithm which enumerates feasible solutions according to an appropriate weighted sum until a condition, ensuring that an optimal solution has been found, is met. The ranking algorithm is based on a branch and bound scheme. We study how to implement efficiently this procedure by considering different algorithmic variants within the procedure: choice of the weighted sum, branching and bounding schemes. We present an experimental analysis that enables us to point out the best variants, and we provide experimental results showing the remarkable efficiency of the procedure, even for large size instances. |
| |
Keywords: | Multi-objective assignment problem Compromise solutions Branch and bound |
本文献已被 ScienceDirect 等数据库收录! |
|