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