TY - JOUR

T1 - A primal-dual interior-point method for facility layout problem with relative-positioning constraints

AU - Ohmori, Shunichi

AU - Yoshimoto, Kazuho

N1 - Publisher Copyright:
© 2021 by the authors. Licensee MDPI, Basel, Switzerland.

PY - 2021/2

Y1 - 2021/2

N2 - We consider the facility layout problem (FLP) in which we find the arrangements of departments with the smallest material handling cost that can be expressed as the product of distance times flows between departments. It is known that FLP can be formulated as a linear programming problem if the relative positioning of departments is specified, and, thus, can be solved to optimality. In this paper, we describe a custom interior-point algorithm for solving FLP with relative positioning constraints (FLPRC) that is much faster than the standard methods used in the general-purpose solver. We build a compact formation of FLPRC and its duals, which enables us to establish the optimal condition very quickly. We use this optimality condition to implement the primal-dual interior-point method with an efficient Newton step computation that exploit special structure of a Hessian. We confirm effectiveness of our proposed model through applications to several well-known benchmark data sets. Our algorithm shows much faster speed for finding the optimal solution.

AB - We consider the facility layout problem (FLP) in which we find the arrangements of departments with the smallest material handling cost that can be expressed as the product of distance times flows between departments. It is known that FLP can be formulated as a linear programming problem if the relative positioning of departments is specified, and, thus, can be solved to optimality. In this paper, we describe a custom interior-point algorithm for solving FLP with relative positioning constraints (FLPRC) that is much faster than the standard methods used in the general-purpose solver. We build a compact formation of FLPRC and its duals, which enables us to establish the optimal condition very quickly. We use this optimality condition to implement the primal-dual interior-point method with an efficient Newton step computation that exploit special structure of a Hessian. We confirm effectiveness of our proposed model through applications to several well-known benchmark data sets. Our algorithm shows much faster speed for finding the optimal solution.

KW - Convex optimization

KW - Facility layout problem

KW - Interior-point method

UR - http://www.scopus.com/inward/record.url?scp=85101253275&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85101253275&partnerID=8YFLogxK

U2 - 10.3390/a14020060

DO - 10.3390/a14020060

M3 - Article

AN - SCOPUS:85101253275

SN - 1999-4893

VL - 14

JO - Algorithms

JF - Algorithms

IS - 2

M1 - 60

ER -