Authors: | Tomić, Milan Urošević, Dragan |
Affiliations: | Computer Science Mathematical Institute of the Serbian Academy of Sciences and Arts |
Title: | A Heuristic Approach in Solving the Optimal Seating Chart Problem | Series/Report no.: | Communications in Computer and Information Science | First page: | 271 | Last page: | 283 | Conference: | MOTOR 2021 : International Conference on Mathematical Optimization Theory and Operations Research | Issue Date: | 1-Jul-2021 | Rank: | M33 | ISBN: | 978-3-030-86432-3 | ISSN: | 1865-0929 | DOI: | 10.1007/978-3-030-86433-0_19 | Abstract: | The optimal seating chart problem is a graph partitioning problem with very practical use. It is the problem of finding an optimal seating arrangement for a wedding or a gala dinner. Given the number of tables available and the number of seats per table, the optimal seating arrangement is determined based on the guests’ preferences to seat or not to seat together with other guests at the same table. The problem is easily translated to finding an m-partitioning of a graph of n nodes, such that the number of nodes in each partition is less than or equal to the given upper limit c, and that the sum of edge weights in all partitions is maximized. Although it can be easily formulated as MILP, the problem is extremely difficult to solve even with relatively small instances, which makes it perfect to apply a heuristic method. In this paper, we present research of a novel descent-ascent method for the solution, with comparison to some of the already proposed techniques from the earlier works. |
Keywords: | Graph partitioning | Seating optimization | Simulated annealing | Publisher: | Springer Link |
Show full item record
SCOPUSTM
Citations
2
checked on Dec 24, 2024
Page view(s)
14
checked on Dec 24, 2024
Google ScholarTM
Check
Altmetric
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.