An algorithm for the three-index assignment problem

An algorithm for the three-index assignment problem

0.00 Avg rating0 Votes
Article ID: iaor1993695
Country: United States
Volume: 39
Issue: 1
Start Page Number: 150
End Page Number: 161
Publication Date: Jan 1991
Journal: Operations Research
Authors: ,
Keywords: programming: integer, queues: applications, networks
Abstract:

The authors describe a branch-and-bound algorithm for solving the axial three-index assignment problem. The main features of the algorithm include a Lagrangian relaxation that incorporates a class of facet inequalities and is solved by a modified subgradient procedure to find good lower bounds, a primal heuristic based on the principle of minimizing maximum regret plus a variable depth interchange phase for finding good upper bounds, and a novel branching strategy that exploits problem structure to fix several variables at each node and reduce the size of the total enumeration tree. Computational experience is reported on problems up to 78 equations and 17576 variables. The primal heuristics were tested on problems with up to 210 equations and 343000 variables.

Reviews

Required fields are marked *. Your email address will not be published.