A Primal-Dual Interior-Point Method for Facility Layout Problem with Relative-Positioning Constraints
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 rela...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-02-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/14/2/60 |
| _version_ | 1827589267252051968 |
|---|---|
| author | Shunichi Ohmori Kazuho Yoshimoto |
| author_facet | Shunichi Ohmori Kazuho Yoshimoto |
| author_sort | Shunichi Ohmori |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-09T00:54:13Z |
| format | Article |
| id | doaj.art-1f173ba99da145a6b9c50806d3b0a3c8 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-09T00:54:13Z |
| publishDate | 2021-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-1f173ba99da145a6b9c50806d3b0a3c82023-12-11T17:00:15ZengMDPI AGAlgorithms1999-48932021-02-011426010.3390/a14020060A Primal-Dual Interior-Point Method for Facility Layout Problem with Relative-Positioning ConstraintsShunichi Ohmori0Kazuho Yoshimoto1Graduate School of Creative Science and Engineering, Waseda University, Tokyo 169-8050, JapanSchool of Creative Science and Engineering, Waseda University, Tokyo 169-8050, JapanWe 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.https://www.mdpi.com/1999-4893/14/2/60facility layout probleminterior-point methodconvex optimization |
| spellingShingle | Shunichi Ohmori Kazuho Yoshimoto A Primal-Dual Interior-Point Method for Facility Layout Problem with Relative-Positioning Constraints Algorithms facility layout problem interior-point method convex optimization |
| title | A Primal-Dual Interior-Point Method for Facility Layout Problem with Relative-Positioning Constraints |
| title_full | A Primal-Dual Interior-Point Method for Facility Layout Problem with Relative-Positioning Constraints |
| title_fullStr | A Primal-Dual Interior-Point Method for Facility Layout Problem with Relative-Positioning Constraints |
| title_full_unstemmed | A Primal-Dual Interior-Point Method for Facility Layout Problem with Relative-Positioning Constraints |
| title_short | A Primal-Dual Interior-Point Method for Facility Layout Problem with Relative-Positioning Constraints |
| title_sort | primal dual interior point method for facility layout problem with relative positioning constraints |
| topic | facility layout problem interior-point method convex optimization |
| url | https://www.mdpi.com/1999-4893/14/2/60 |
| work_keys_str_mv | AT shunichiohmori aprimaldualinteriorpointmethodforfacilitylayoutproblemwithrelativepositioningconstraints AT kazuhoyoshimoto aprimaldualinteriorpointmethodforfacilitylayoutproblemwithrelativepositioningconstraints AT shunichiohmori primaldualinteriorpointmethodforfacilitylayoutproblemwithrelativepositioningconstraints AT kazuhoyoshimoto primaldualinteriorpointmethodforfacilitylayoutproblemwithrelativepositioningconstraints |