Accession Number:

AD0742352

Title:

A Linear Programming Formulation of a Special Quadratic Assignment Problem

Descriptive Note:

Research rept.

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s):

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

Report Date:

1971-11-01

Pagination or Media Count:

27.0

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.

Descriptors:

• *LINEAR PROGRAMMING
• ALGORITHMS
• SET THEORY
• THEOREMS
• SIMPLEX METHOD
• MATRICES(MATHEMATICS)

Subject Categories:

• Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE