An exact penalty function method for optimising QAP formulation in facility layout problem
MetadataShow full item record
© 2016 Informa UK Limited, trading as Taylor & Francis GroupA quadratic assignment problem (QAP), which is a combinatorial optimisation problem, is developed to model the problem of locating facilities with material flows between them. The aim of solving the QAP formulation for a facility layout problem (FLP) is to increase a system’s operating efficiency by reducing material handling costs, which can be measured by interdepartmental distances and flows. The QAP-formulated FLP can be viewed as a discrete optimisation problem, where the quadratic objective function is optimised with respect to discrete decision variables subject to linear equality constraints. The conventional approach for solving this discrete optimisation problem is to use the linearisation of the quadratic objective function whereby additional discrete variables and constraints are introduced. The adoption of the linearisation process can result in a significantly increased number of variables and constraints; solving the resulting problem can therefore be challenging. In this paper, a new approach is introduced to solve this discrete optimisation problem. First, the discrete optimisation problem is transformed into an equivalent nonlinear optimisation problem involving only continuous decision variables by introducing quadratic inequality constraints. The number of variables, however, remains the same as the original problem. Then, an exact penalty function method is applied to convert this transformed continuous optimisation problem into an unconstrained continuous optimisation problem. An improved backtracking search algorithm is then developed to solve the unconstrained optimisation problem. Numerical computation results demonstrate the effectiveness of the proposed new approach.
Showing items related by title, author, creator and subject.
Li, Bin (2011)In this thesis, we consider several types of optimal control problems with constraints on the state and control variables. These problems have many engineering applications. Our aim is to develop efficient numerical methods ...
Yu, Changjun (2012)In this thesis, We propose new computational algorithms and methods for solving four classes of constrained optimization and optimal control problems. In Chapter 1, we present a brief review on optimization and ...
Ruan, Ning (2012)Duality is one of the most successful ideas in modern science  . It is essential in natural phenomena, particularly, in physics and mathematics   . In this thesis, we consider the canonical duality ...