4 ms·

Isn't "Keep people either together or apart" an NP-Hard problem, and basically unsolvable for more than a couple preferences?

tunnuz 3y ago
Finding solutions that are not necessarily optimal but good in practice is often a tractable problem.
- haroldp 3y ago
  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? :)
  - stncls 3y ago
    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/ 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.
teejae 3y ago
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.
- stncls 3y ago
  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?
  - teejae 3y ago
    I'm using Optaplanner as the engine under the covers, which is open source and off the shelf. https://www.optaplanner.org/ https://www.optaplanner.org/
stncls 3y ago
Solving this problem to optimality (for whatever constraints and objective function one is interested in -- a precise formulation was not given by the O.P.) is presumably NP-hard indeed, meaning that the computational cost grows exponentially with the size of the problem (in practice: the number of invitees). However, 1. This is only an asymptotic argument. For "small" size, these problems can be tackled. People routinely solve this type of problem (namely: mixed-integer optimization problems), with up to hundreds of thousands of variables, to proven optimality, in a matter of minutes (see [1]). In this case, it looks like an assignment problem in which the number of variables would be (number of invitees) times (number of tables), so for up to 1000 invitees and 100 tables, there is a chance the problem can be solved optimally. 2. The O.P. is most likely looking heuristically for good solutions, not optimal ones. And I can't really blame them for that. Do we really care about optimality here? [1] https://plato.asu.edu/ftp/milp.html https://plato.asu.edu/ftp/milp.html
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 ago
  I 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 ago
  I 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).
hermitcrab 3y ago
>Isn't "Keep people either together or apart" an NP-Hard problem, Yes. >and basically unsolvable for more than a couple preferences? Our PerfectTablePlan table planner can optimize seating for thousands of guests with thousands of preference constraints (between individuals and groups) on a standard desktop PC/Mac. It uses a genetic algorithm to quickly produce a 'good enough' (but not guaranteed to be optimal) solution. For seating plans it isn't really clear what the optimum is anyway. It is more important that than Bob sits next to Jill or not next to Jack or not next to an empty seats? Debatable.

tunnuz 3y ago

Finding solutions that are not necessarily optimal but good in practice is often a tractable problem.

haroldp 3y ago
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? :)
- stncls 3y ago
  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/ 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.

teejae 3y ago

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.

stncls 3y ago
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?
- teejae 3y ago
  I'm using Optaplanner as the engine under the covers, which is open source and off the shelf. https://www.optaplanner.org/ https://www.optaplanner.org/

stncls 3y ago

Solving this problem to optimality (for whatever constraints and objective function one is interested in -- a precise formulation was not given by the O.P.) is presumably NP-hard indeed, meaning that the computational cost grows exponentially with the size of the problem (in practice: the number of invitees). However, 1. This is only an asymptotic argument. For "small" size, these problems can be tackled. People routinely solve this type of problem (namely: mixed-integer optimization problems), with up to hundreds of thousands of variables, to proven optimality, in a matter of minutes (see [1]). In this case, it looks like an assignment problem in which the number of variables would be (number of invitees) times (number of tables), so for up to 1000 invitees and 100 tables, there is a chance the problem can be solved optimally. 2. The O.P. is most likely looking heuristically for good solutions, not optimal ones. And I can't really blame them for that. Do we really care about optimality here? [1] https://plato.asu.edu/ftp/milp.html https://plato.asu.edu/ftp/milp.html

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 ago
I 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 ago
I 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).

hermitcrab 3y ago

>Isn't "Keep people either together or apart" an NP-Hard problem, Yes. >and basically unsolvable for more than a couple preferences? Our PerfectTablePlan table planner can optimize seating for thousands of guests with thousands of preference constraints (between individuals and groups) on a standard desktop PC/Mac. It uses a genetic algorithm to quickly produce a 'good enough' (but not guaranteed to be optimal) solution. For seating plans it isn't really clear what the optimum is anyway. It is more important that than Bob sits next to Jill or not next to Jack or not next to an empty seats? Debatable.