An Algorithm for the Three-Index Assignment Problem

Egon Balas and Matthew J. Saltzman
Additional contact information
Matthew J. Saltzman: Clemson University, Clemson, South Carolina

Operations Research, 1991, vol. 39, issue 1, 150-161

Abstract: We 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 with up to 78 equations and 17,576 variables. The primal heuristics were tested on problems with up to 210 equations and 343,000 variables.

Keywords: networks/graphs; matchings: three-dimensional; programming; integer algorithms: primal heuristics; queues; optimization: subgradient optimization with facet defining cutting planes (search for similar items in EconPapers)
Date: 1991
References: Add references at CitEc
Citations: View citations in EconPapers (21)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.39.1.150 (application/pdf)

Related works:
Working Paper: AN ALGORITHM FOR THE THREE-INDEX ASSIGNMENT PROBLEM (1988)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:39:y:1991:i:1:p:150-161

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().