Looking for a algorithm to optimize game convention table allocations
October 5, 2019 4:30 PM Subscribe
Given several rooms of varying sizes with rows of tables of varying lengths, I'm trying to programmatically solve the problem of optimally allocating tables to events. This seems like a variation on the bin packing problem, but I want to keep all "boxes" of same event contiguously grouped.
This is for trying to optimize space usage at a gaming convention where there are many events that requires different sizes of play area.
Example:
- Say there is a room with 4 rows of tables each 4ft wide and 42ft long.
- Event Foo requires 15 sets of 4ftx7ft play spaces
- Event Bar requires 12 sets of 4ftx4ft play spaces
I could fit 6 Foo areas in one of my 42 rows, so 15 sets would take 2 full rows and 14ft of a 3rd row (leaving 28ft). I can fit 8 Bar areas in one 42ft row, the remaining 4 would take 16 ft. So, I can fit all of these events in my room and have a 4ft x 12ft space to spare.
I am looking for a way to programmatically do this kind of calculation so I can do it at scale for many rooms and dozens of events.
At first glance this looks like a simple bin packing problem, but it has the added wrinkle that all the spaces for one event should all be together. I found a paper that uses package destination as another variable. It might be analogous to my keep them together requirement. But I'm looking for ideas of either algorithms or (even better) some existing implementation of libraries (preferably node.js or C#).
This is for trying to optimize space usage at a gaming convention where there are many events that requires different sizes of play area.
Example:
- Say there is a room with 4 rows of tables each 4ft wide and 42ft long.
- Event Foo requires 15 sets of 4ftx7ft play spaces
- Event Bar requires 12 sets of 4ftx4ft play spaces
I could fit 6 Foo areas in one of my 42 rows, so 15 sets would take 2 full rows and 14ft of a 3rd row (leaving 28ft). I can fit 8 Bar areas in one 42ft row, the remaining 4 would take 16 ft. So, I can fit all of these events in my room and have a 4ft x 12ft space to spare.
I am looking for a way to programmatically do this kind of calculation so I can do it at scale for many rooms and dozens of events.
At first glance this looks like a simple bin packing problem, but it has the added wrinkle that all the spaces for one event should all be together. I found a paper that uses package destination as another variable. It might be analogous to my keep them together requirement. But I'm looking for ideas of either algorithms or (even better) some existing implementation of libraries (preferably node.js or C#).
Err, you know that there is actual table planning software for event planners, right? Like by all means write a program to solve the Knapsack Problem is you want, but you can also just... spend ten bucks and let the internet solve it for you.
posted by DarlingBri at 4:57 PM on October 5, 2019
posted by DarlingBri at 4:57 PM on October 5, 2019
Response by poster: @darlingbri, do you have any recommendations for software?
posted by Kolath at 5:14 PM on October 5, 2019
posted by Kolath at 5:14 PM on October 5, 2019
I think when you’re considering trying to optimize heuristic algorithms for problems that are NP-hard, and you’re not already an expert in the field, and the problem size is moderate, and you have additional constraints that make the problem even harder...
I think your best bet is staring at it for a few hours and using the highly optimized neural network in your head to find a decently acceptable solution. Sorry.
posted by SaltySalticid at 6:07 PM on October 5, 2019 [2 favorites]
I think your best bet is staring at it for a few hours and using the highly optimized neural network in your head to find a decently acceptable solution. Sorry.
posted by SaltySalticid at 6:07 PM on October 5, 2019 [2 favorites]
@Kolath Maybe try Magic Table Planner?
(I don't actually understand your problem but table planning, even with different sized tables, is a solved problem. On re-reading, is room planning what you actually need? Regardless, there's an event planning solution on the internet for all event-planning needs.)
posted by DarlingBri at 6:26 AM on October 6, 2019
(I don't actually understand your problem but table planning, even with different sized tables, is a solved problem. On re-reading, is room planning what you actually need? Regardless, there's an event planning solution on the internet for all event-planning needs.)
posted by DarlingBri at 6:26 AM on October 6, 2019
Response by poster: @SaltySalticid, yes, that's the default option since it's what I've been doing with this convention for the last several years. I'm just trying to see if anyone has suggestions for how to apply math to make it a bit easier (slash also I derive joy from trying to apply technology to problems like this).
@DarlingBri, thank you for following up! Let me try a different analogy to explain. Consider a game of chess, two players, pretty small play area needed, maybe 3ft by 2 ft. Another board game like Monopoly takes 4 players and has lots more stuff to they probably need a space that is 3ft by 5ft to fit everything. If I have a room full of long rows of tables, I'm trying to use math to say: Okay if I have 100 chess games in a tournament and at the same time 20 Monopoly games in a tournament, will they fit in this room? And if yes, what is the best layout that gives everyone space and keeps like games near each other.
I don't need help doing the physical layouts of the halls (I already have that in a CAD program). I need help with matching the games to the hall layouts in a way that makes most effective use of space.
posted by Kolath at 7:37 AM on October 6, 2019
@DarlingBri, thank you for following up! Let me try a different analogy to explain. Consider a game of chess, two players, pretty small play area needed, maybe 3ft by 2 ft. Another board game like Monopoly takes 4 players and has lots more stuff to they probably need a space that is 3ft by 5ft to fit everything. If I have a room full of long rows of tables, I'm trying to use math to say: Okay if I have 100 chess games in a tournament and at the same time 20 Monopoly games in a tournament, will they fit in this room? And if yes, what is the best layout that gives everyone space and keeps like games near each other.
I don't need help doing the physical layouts of the halls (I already have that in a CAD program). I need help with matching the games to the hall layouts in a way that makes most effective use of space.
posted by Kolath at 7:37 AM on October 6, 2019
This thread is closed to new comments.
- You have 168ft of table.
- Foo requires 15x7=105ft
- Event Bar requires 12x4ft=48ft
Writing a knapsack solver is a first year CS problem. You should be able to find one in any language.
You didn’t mention this in the example but I assume you have multiple rooms. That makes the entire convention a multiple knapsack problem (where each room is a knapsack).
So far so good, but the reason I say “very similar to a knapsack problem” is the knapsack solver doesn’t know tables are 42 ft long or, eg the 105ft of foo cannot be split at arbitrary places. So it may suggest solutions that require 3ft of foo at the end of one row and 4ft at the start of another. You can fix this by treating each table as a knapsack but that introduces other problems.
TLDR: take a look at the wiki page for List of knapsack problem and you might find a match. Alternatively, this is a good question for stack overflow!
posted by caek at 4:51 PM on October 5, 2019 [1 favorite]