A Semidefinite Approach for the Single Row Facility Layout Problem

Jan Schwiddessen ()
Additional contact information
Jan Schwiddessen: Alpen-Adria-Universität Klagenfurt

A chapter in Operations Research Proceedings 2021, 2022, pp 45-51 from Springer

Abstract: Abstract This paper summarizes several results from the author’s Master’s thesis. We propose a new semidefinite approach for the $$\mathcal NP$$ N P -hard single row facility layout problem (SRFLP) which is the problem of arranging n facilities of given lengths on a straight line, while minimizing a weighted sum of distances between all facility pairs. We tighten existing semidefinite relaxations with further inequalities and use an algorithmic method not yet considered for the SRFLP. Our new approach outperforms all other approaches in the literature and significantly reduces the best known duality gaps for all unsolved benchmark instances with $$n\le 100$$ n ≤ 100 . Many instances with up to $$n=81$$ n = 81 are solved for the first time.

Keywords: Single row facility layout; Semidefinite optimization (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:lnopch:978-3-031-08623-6_8

Ordering information: This item can be ordered from
http://www.springer.com/9783031086236

DOI: 10.1007/978-3-031-08623-6_8

Access Statistics for this chapter

More chapters in Lecture Notes in Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().