{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T01:49:12Z","timestamp":1760233752193,"version":"build-2065373602"},"reference-count":44,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2021,2,13]],"date-time":"2021-02-13T00:00:00Z","timestamp":1613174400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.3390\/a14020060","type":"journal-article","created":{"date-parts":[[2021,2,14]],"date-time":"2021-02-14T02:08:12Z","timestamp":1613268492000},"page":"60","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["A Primal-Dual Interior-Point Method for Facility Layout Problem with Relative-Positioning Constraints"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2635-0450","authenticated-orcid":false,"given":"Shunichi","family":"Ohmori","sequence":"first","affiliation":[{"name":"Graduate School of Creative Science and Engineering, Waseda University, Tokyo 169-8050, Japan"}]},{"given":"Kazuho","family":"Yoshimoto","sequence":"additional","affiliation":[{"name":"School of Creative Science and Engineering, Waseda University, Tokyo 169-8050, Japan"}]}],"member":"1968","published-online":{"date-parts":[[2021,2,13]]},"reference":[{"key":"ref_1","unstructured":"Tompkins, J.A., White, J.A., Bozer, Y.A., and Tanchoco, J.M.A. (2010). Facilities Planning, John Wiley & Sons."},{"key":"ref_2","unstructured":"Richard, M., and Hales, L. (2021, February 09). Systematic Layout Planning. Available online: http:\/\/hpcinc.com\/wp-content\/uploads\/2016\/07\/Systematic-Layout-Planning-SLP-4th-edition-soft-copy.pdf."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/0360-8352(85)90013-0","article-title":"Facilities layout: A survey of solution procedures","volume":"9","author":"Levary","year":"1985","journal-title":"Comput. Ind. Eng."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0377-2217(87)90238-4","article-title":"The facility layout problem","volume":"29","author":"Kusiak","year":"1987","journal-title":"Eur. J. Oper. Res."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"2559","DOI":"10.1080\/00207549408957084","article-title":"Machine layout problem in modern manufacturing facilities","volume":"32","author":"Hassan","year":"1994","journal-title":"Int. J. Prod. Res."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1016\/0278-6125(96)84198-7","article-title":"The facility layout problem: Recent and emerging trends and perspectives","volume":"15","author":"Meller","year":"1996","journal-title":"J. Manuf. Syst."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/j.arcontrol.2007.04.001","article-title":"Facility layout problems: A survey","volume":"31","author":"Drira","year":"2007","journal-title":"Annu. Rev. Control"},{"key":"ref_8","first-page":"44","article-title":"Analysis of unequal areas facility layout problems","volume":"4","author":"Arikaran","year":"2010","journal-title":"Int. J. Eng."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ejor.2017.01.049","article-title":"Mathematical optimization approaches for facility layout problems: The state-of-the-art and future research directions","volume":"261","author":"Anjos","year":"2017","journal-title":"Eur. J. Oper. Res."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"957","DOI":"10.1007\/s00170-017-0895-8","article-title":"Classification of facility layout problems: A review study","volume":"94","author":"Fereidouni","year":"2018","journal-title":"Int. J. Adv. Manuf. Technol."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"53","DOI":"10.2307\/1907742","article-title":"Assignment Problems and the Location of Econmic Activities","volume":"25","author":"Koopmans","year":"1957","journal-title":"Econometrica"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1080\/07408170600844108","article-title":"A sequence-pair representation and MIP-model-based heuristic for the facility layout problem with rectangular departments","volume":"39","author":"Liu","year":"2007","journal-title":"IIE Trans."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1016\/0377-2217(92)90041-7","article-title":"A nonlinear optimization approach for solving facility layout problems","volume":"57","author":"Carter","year":"1992","journal-title":"Eur. J. Oper. Res."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s001860200197","article-title":"An attractor-repeller approach to floorplanning","volume":"56","author":"Anjos","year":"2002","journal-title":"Math. Methods Oper. Res."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1287\/ijoc.1040.0103","article-title":"A new mathematical-programming framework for facility-layout design","volume":"18","author":"Anjos","year":"2006","journal-title":"INFORMS J. Comput."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/j.ejor.2011.04.013","article-title":"A convex optimisation framework for the unequal-areas facility layout problem","volume":"214","author":"Jankovits","year":"2011","journal-title":"Eur. J. Oper. Res."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1379","DOI":"10.1007\/s11590-016-1008-6","article-title":"An improved two-stage optimization-based framework for unequal-areas facility layout","volume":"10","author":"Anjos","year":"2016","journal-title":"Optim. Lett."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1016\/0377-2217(92)90034-7","article-title":"Genetic algorithms, function optimization, and facility layout design","volume":"63","author":"Tam","year":"1992","journal-title":"Eur. J. Oper. Res."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"3739","DOI":"10.1080\/002075499190022","article-title":"An iterative facility layout algorithm","volume":"37","author":"Gau","year":"1999","journal-title":"International J. Prod. Res."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"4055","DOI":"10.1080\/00207540410001716471","article-title":"Genetic algorithm for facilities layout problems based on slicing tree structure","volume":"42","author":"Shayan","year":"2004","journal-title":"Int. J. Prod. Res."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/j.ejor.2008.06.028","article-title":"STaTS: A slicing tree and tabu search based heuristic for the unequal area facility layout problem","volume":"197","author":"Scholz","year":"2009","journal-title":"Eur. J. Oper. Res."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/j.eswa.2017.02.047","article-title":"Harmony search for the layout design of an unequal area facility","volume":"79","author":"Kang","year":"2017","journal-title":"Expert Syst. Appl."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1080\/07408179508936763","article-title":"Unequal-area facility layout by genetic search","volume":"27","author":"Tate","year":"1995","journal-title":"IIE Trans."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"918","DOI":"10.1016\/j.ejor.2004.08.026","article-title":"Multi-objective tabu search using a multinomial probability mass function","volume":"169","author":"Smith","year":"2006","journal-title":"Eur. J. Oper. Res."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"5523","DOI":"10.1016\/j.eswa.2009.12.080","article-title":"Solving facility layout problems using flexible bay structure representation and ant system algorithm","volume":"37","author":"Wong","year":"2010","journal-title":"Expert Syst. Appl."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1263","DOI":"10.1080\/0305215X.2010.548864","article-title":"A new relaxed flexible bay structure representation and particle swarm optimization for the unequal area facility layout problem","volume":"43","author":"Konak","year":"2011","journal-title":"Eng. Optim."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1877","DOI":"10.1080\/00207541003614371","article-title":"Unequal area flexible bay facility layout using ant colony optimisation","volume":"49","author":"Konak","year":"2011","journal-title":"Int. J. Prod. Res."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/j.eswa.2016.10.004","article-title":"An island model genetic algorithm for unequal area facility layout problems","volume":"68","year":"2017","journal-title":"Expert Syst. Appl."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"112819","DOI":"10.1016\/j.eswa.2019.07.036","article-title":"Applying the coral reefs optimization algorithm for solving unequal area facility layout problems","volume":"138","year":"2019","journal-title":"Expert Syst. Appl."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"103445","DOI":"10.1016\/j.engappai.2019.103445","article-title":"A novel Island Model based on Coral Reefs Optimization algorithm for solving the unequal area facility layout problem","volume":"89","year":"2020","journal-title":"Eng. Appl. Artif. Intell."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/j.eswa.2018.02.035","article-title":"Multi-objective particle swarm optimization algorithm based on objective space division for the unequal-area facility layout problem","volume":"102","author":"Liu","year":"2018","journal-title":"Expert Syst. Appl."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/j.jmsy.2019.09.004","article-title":"Multi-objective particle swarm optimization for multi-workshop facility layout problem","volume":"53","author":"Guan","year":"2019","journal-title":"J. Manuf. Syst."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1016\/j.ejor.2016.11.011","article-title":"Dynamic facility layout problem based on open queuing network theory","volume":"259","author":"Pourvaziri","year":"2017","journal-title":"Eur. J. Oper. Res."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/j.eswa.2018.01.011","article-title":"A new hybrid heuristic algorithm based on bacterial foraging optimization for the dynamic facility layout problem","volume":"98","author":"Turanoglu","year":"2018","journal-title":"Expert Syst. Appl."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"621","DOI":"10.1007\/s10479-016-2351-9","article-title":"Formulating and solving sustainable stochastic dynamic facility layout problem: A key to sustainable operations","volume":"253","author":"Tayal","year":"2017","journal-title":"Ann. Oper. Res."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1016\/j.jmsy.2016.12.008","article-title":"A dynamic multi-objective approach for the reconfigurable multi-facility layout problem","volume":"42","author":"Azevedo","year":"2017","journal-title":"J. Manuf. Syst."},{"key":"ref_37","first-page":"49","article-title":"An integrated simulation-based optimization technique for multi-objective dynamic facility layout problem","volume":"8","author":"Pourhassan","year":"2017","journal-title":"J. Ind. Inf. Integr."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Montreuil, B. (1991). A modelling framework for integrating layout design and flow network design. Material Handling\u2019 90, Springer.","DOI":"10.1007\/978-3-642-84356-3_8"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/S0167-6377(98)00024-8","article-title":"Optimal facility layout design","volume":"23","author":"Meller","year":"1998","journal-title":"Oper. Res. Lett."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1287\/opre.51.4.629.16096","article-title":"Enhanced model formulations for optimal facility layout","volume":"51","author":"Sherali","year":"2003","journal-title":"Oper. Res."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1016\/S0305-0548(03)00246-6","article-title":"An \u03b5-accurate model for optimal unequal-area block layout design","volume":"32","author":"Castillo","year":"2005","journal-title":"Comput. Oper. Res."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1016\/j.ejor.2011.10.052","article-title":"A graph-pair representation and MIP-model-based heuristic for the unequal-area facility layout problem","volume":"218","author":"Bozer","year":"2012","journal-title":"Eur. J. Oper. Res."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1016\/j.cie.2016.10.016","article-title":"Layout design problems with heterogeneous area constraints","volume":"102","author":"Chae","year":"2016","journal-title":"Comput. Ind. Eng."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Boyd, S., and Vandenberghe, L. (2004). Convex Optimization, Cambridge University Press.","DOI":"10.1017\/CBO9780511804441"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/2\/60\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:23:56Z","timestamp":1760160236000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/2\/60"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,13]]},"references-count":44,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2021,2]]}},"alternative-id":["a14020060"],"URL":"https:\/\/doi.org\/10.3390\/a14020060","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,2,13]]}}}