4 ms·
It's probably an optimization problem with multiple parameters so you're never looking for an exact solution. But as the NP-hardness of that problem goes: Say
by maweki 3y ago
It's probably an optimization problem with multiple parameters so you're never looking for an exact solution.
But as the NP-hardness of that problem goes: Say you have 400 guests on 50 tables and you probably expect multiple solutions, you're looking at maybe 20K variables in a SAT encoding. That's an industrial scale SAT problem but very much not untractable.
The question is, whether we would usually expect a number of solutions in the thousands or whether we expect just a handful. I'd guess its the former, as many people on the "cheap tables" are really interchangeable and not subject to many constraints. So usually you'd looking at just a handful of tables and guests that are difficult to place. That begs the question whether the problem OP's trying to solve is really a problem people have difficulties solving (or isn't easily solved by adding a table or two).
- teejae 3y agoI have a friend who had 400+ guests and 50+ tables. But they paid by the table, so saving whole tables would have saved lots of money. And friend stayed up all night before wedding stressing about who to put where.
- noduerme 3y agoI had to write a piece of code to manage 200+ dogs at a kenneling facility, sorted by temperament, across a Gantt chart, with lists of friends and enemies which could stay together or must never be together - coming and going at different times. Additionally, dogs and kennels are both color-coded and certain types of dogs can only stay in certain types of kennels. Some dogs cannot share a kennel at all; kennels have a max limit of 1, 2 or 3 dogs; and some kennels are premium-priced. In practice, the "optimal" solution depends on what you're optimizing for. In my case, it was maximizing the number of dogs that could board on any given night. This involved looking for open paths - since dogs can be moved around daily if necessary. Then rule out any based on the constraints: Prevent enemy conflict, limit to max occupancy, etc. After that, the preference is for boarding them in a kennel with a friend if possible, however there are trade-offs here in whether this creates too many extra moves... e.g. if a friend is coming in for one night of a dog's 7-night stay, we don't prefer to move. So the third priority, which occasionally overrides the second priority, is minimizing the number of moves which add work for employees. To do that, we look for the longest stretch open at each move branch, ranking them by number of friends descending, barring any with enemies. As you can imagine, this was way too complicated and branching, so the system prunes the option tree at each necessary move down to a few dozen possibilities and continues down each of those paths, then ranks all the paths for the user to choose from. In other words, a lot of the decisions for optimizing it (in the non-mathematical sense) were about limiting its output to a manageable number of reasonably good choices. Enemies create a hard limit on the number of spots available. Friends are optional (but good for business).
- haroldp 3y agoI was once asked to code a people-matching function where participants had long "don't match me with her" lists and coded a very naive brute force solver that absolutely pegged the CPU on my dev box until I wised up that it was an NP-Hard problem.
- noduerme 3y agoYeah, that's a different and larger problem space. A reservation-maximizing algo doesn't need to come up with a solution for all-vs-all, it only needs to solve for the new reservations you're trying to book vs what's already there; essentially one-vs-all. As it is, searching the tree can take 1-2 seconds in-browser on reasonable hardware, and that's with a good deal of pruning. Trying to massively re-optimize the whole calendar after the fact would be undesirable anyway, considering there are a lot of human choices being made along the way.
- hermitcrab 3y agoThat sounds amazingly high tech for a kenneling facility. How did you do the optimization - usign an off-the-shelf solver?
- noduerme 3y agoI wrote it completely from scratch, basically a custom type of tree search. Admittedly there are naive aspects and opinionated optimizations and magical constants involved in the final code, but in practice it's worked without any problems for 4-5 years, and it's relatively fast for the amount of data it's churning. [Edit: An example of a magical constant is the weighting of "friends" over a period of time versus "number of moves" required to achieve optimal friendships]
- hermitcrab 3y agoImpressive. Also hilarious that this kennel is probably better optimized than a lot of big logistics companies. ;0) I think arbitary weightings are unavoidable when optimizing 'soft' (social) problems like kennel allocation or seating plans. The optimal solution is not well defined.