Cool to see a project using optimisation <3
Yep! I was scratching an optimization itch. Glad to see someone noticed!
Do you have a writeup about the optimization methods you used? I mean, which algorithms did you choose?
Show HN: Better Seater – Wedding seating chart optimizer
21–30 of 108 posts
Re: Show HN: Better Seater – Wedding seating chart optimizer
#22I tried writing one of these about 10 years ago and failed miserably.
It was a generalized banquet hall/dinner/wedding seating chart.
The one that I was looking to write involved the following specs:
- friends and +1s sit together
- guests could sign up as a "group" (Tom's group) and sit together
- cluster people from the same area, or not even close to the same area
- some guests need to be prioritized as close to the front of the room/stage/guest(s)-of-honor
These were very difficult specs to satisfy and not getting it right was not an option since folks were paying $50 a plate with ~600 guests. The solution has always been to do it by hand.
Re: Show HN: Better Seater – Wedding seating chart optimizer
#23Requirements for the Seating Chart Optimizer I made for planning my wedding party: * 120 guests: 49 couples and 22 singles * To be seated at 11-ish tables of 8, 10, 12 people each (by combining 4- and 6-person tables) * Couples must be seated at the same table * Plan only needs to say which guests sit at which tables - individual placement at the table will be decided just-in-time by the people putting the name cards…
Thanks for trying it out!
With the spreadsheet, you can just put couples as single guest (+1 = 2 party size). So you can put a whole family as (Person+3) or something. See the template.
The "couple" was really the wedding couple as example.
I'm optimizing for probably 100+ guests.
Hope that makes sense!
Re: Show HN: Better Seater – Wedding seating chart optimizer
#24Simply contemplating having to do this is one of the reasons I'm very happy that the local standard for weddings (even big, expensive, nighttime ones) in my hometown was buffet service with available but unassigned seating. People hang out with who they want to, as much as they want to, and can just avoid those who bother them.
Re: Show HN: Better Seater – Wedding seating chart optimizer
#25Isn't "Keep people either together or apart" an NP-Hard problem, and basically unsolvable for more than a couple preferences?
Yep, NP-hard! This is using an optimization engine. It's not brute forcing. But hopefully it's getting pretty good approximate results. You can keep trying harder from the state, just click again on the Optimize buttons. I admit, I haven't optimized the optimizer yet.
What do you mean by optimization engine? Did you write a solver yourself, or did you use something off-the-shelf? In either case, what are the algorithms involved?
Re: Show HN: Better Seater – Wedding seating chart optimizer
#26This is interesting. What's the algorithm that you use to optimize?
Re: Show HN: Better Seater – Wedding seating chart optimizer
#27Earlier quoted context omitted.
Finding solutions that are not necessarily optimal but good in practice is often a tractable problem.
For sure: a traveling salesman route under length L, for instance. But what is good enough when combining incompatible people? Less than three vendettas per table? :)
I agree with grandparent that non-optimal solutions are often enough.
But just to be complete, since TSP was mentioned here:
We could solve TSP instances with >80k cities to optimality back in 2006:
https://www.math.uwaterloo.ca/tsp/
The trick is that some types of problems, like TSP or assignment problems, have structure that can be exploited. Of course they remain NP-hard, so as size grows, at some point the computational cost becomes unsustainable. But the point at which this happens is often way further (i.e. for much larger instances) than most imagine.
Re: Show HN: Better Seater – Wedding seating chart optimizer
#28I tried writing one of these about 10 years ago and failed miserably. It was a generalized banquet hall/dinner/wedding seating chart. The one that I was looking to write involved the following specs: - friends and +1s sit together - guests could sign up as a "group" (Tom's group) and sit together - cluster people from the same area, or not even close to the same area - some guests need to be prioritized as close to t…
I agree there's going to be some hand curation. That's why this tool was meant to help iterate over solutions, and not prescribe. You can lock people in.
Also, thanks for the specs. I was thinking of some of those things, but really glad to hear how you thought about it!
I haven't clustered people together yet in terms of physical location, because I don't have a way to express table locations yet in the UI. Trying to keep it "just simple enough". But I know it's important for many people.
If you have any more insights, I would love to hear it!
Re: Show HN: Better Seater – Wedding seating chart optimizer
#29This looks so much like the bin packing problem [0] if you generalized it you could do a lot with it. [0] https://en.wikipedia.org/wiki/Bin_packing_problem
Yep, I'm targeting an optimization engine at a more specific problem that might be useful to lots of consumers.
Would you make that open source? I'm interested in this problem. I'm sure there are some OS bin packing algorithms but I not familiar with ones that have separation and linking rules.
Re: Show HN: Better Seater – Wedding seating chart optimizer
#30Earlier quoted context omitted.
Yep! I was scratching an optimization itch. Glad to see someone noticed!
Do you have a writeup about the optimization methods you used? I mean, which algorithms did you choose?
No writeup yet, since I've been working on the UX more than the optimization. I haven't optimized the optimizer yet or done benchmarking yet.
Mostly working on the constraints and what's important first to be able to tweak first. Trying to make this very user friendly.