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
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


checked on Jun 11, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.