African Journal of
Agricultural Research

  • Abbreviation: Afr. J. Agric. Res.
  • Language: English
  • ISSN: 1991-637X
  • DOI: 10.5897/AJAR
  • Start Year: 2006
  • Published Articles: 6574

Review

Reducing the number of new constraints and variables in a linearised quadratic assignment problem

Elias Munapo
Department of Decisions Sciences, University of South Africa, P. O. Box 392, Unisa 0003, Pretoria, South Africa.
Email: [email protected]

  •  Accepted: 23 January 2012
  •  Published: 05 June 2012

Abstract

The quadratic assignment problem is a well known difficult discrete combinatorial optimization problem. The problem seeks to locate n facilities among n fixed locations in the most economical way. We propose a technique to reduce the number of new constraints and variables in a linearised quadratic assignment problem. It is computationally cheaper to solve a mathematical model with half the number of new constraints and variables than the original full model. The quadratic assignment problem is common in agricultural resource or facility location, economics, production, military operations or operations research in general.

 

Key words: Linearised quadratic assignment problem, discrete optimization, NP hard, heuristic, lower bound.