Heuristic and exact algorithms for the simultaneous assignment problem

Takeo Yamada

doi:10.1016/S0377-2217(99)00100-9

Return

Heuristic and exact algorithms for the simultaneous assignment problem

2000-06-01

PRE

Takeo Yamada

Yasushi Nasu

DOI：10.1016/S0377-2217(99)00100-9

Original

Original request for help

Save

Abstract

En 中文

The simultaneous assignment problem is formulated as an extension to the assignment problem. The problem is proved, NP-hard. We evaluate its lower bound and present some approximate algorithms. Also we introduce the pegging test to this problem and show that this remarkably reduces the size of the original problem. Combining these we give an algorithm to solve the problem to optimality, and through numerical tests analyze the behavior of the developed algorithms. Randomly generated test problems with up to 48 000 variables are solved in less than a few minutes. (C) 2000 Elsevier Science B.V. All rights reserved.

Keywords:

simultaneous assignment problem

local search

pegging test

combinatorial optimization

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.