A Linear Programming Formulation of a Special Quadratic Assignment Problem

Abstract

A special quadratic assignment problem is shown to be equivalent to a linear programming problem with n cubed constraints and n squared variables where n is the number of elements to be assigned. A labeling algorithm similar to that for the linear transportation problem is presented for solving the problem. An example is presented that deals with ' triangularizing' input-output matrices.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1971
Accession Number
AD0742352

Entities

People

  • D. A. Pierce
  • E. Ramsey
  • V. J. Bowman

Organizations

  • Carnegie Mellon University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computer Programming
  • Engineering
  • Heuristic Methods
  • Industrial Engineering
  • Linear Programming
  • Military Research
  • Permutations
  • Quadratic Programming
  • Schools
  • Simplex Method
  • Systems Engineering
  • Transportation
  • Universities

Fields of Study

  • Mathematics

Readers

  • Linear Algebra
  • Operations Research