An Algorithm for the Three-Index Assignment Problem

Abstract

A branch and bound algorithm is described for solving the axial three-index assignment problem. The main features of the algorithm include a Lagrangian relaxation incorporating a class of facet inequalities and solved by a modified subgradient procedure to find a 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 16,376 variables. The primal heuristics were tested on problems with up to 210 equations and 343,000 variables.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1988
Accession Number
ADA205172

Entities

People

  • Egon Balas
  • Matthew J. Saltzman

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Space

DTIC Thesaurus Topics

  • Algorithms
  • Capital Investments
  • Computations
  • Computer Programming
  • Inequalities
  • Integer Programming
  • Iterations
  • Lagrangian Functions
  • Military Research
  • Optimization
  • Rolling Mills
  • Simplex Method
  • Terminals
  • Transportation
  • Trees (Data Structures)
  • Two Dimensional
  • Universities

Readers

  • Operations Research