What algorithm can be used for a more complex version of the bin packing problem?

Question

I'm currently developing a plugin for World of Warcraft in LUA to help optimize a recently introduced part of the game, namely Garrison missions.

A Warcraft Garrison (basically a player fortress) has a place where you can assign your followers to go on an mission for you. If these missions succeed, your followers get some experience and you get a small reward, ranging from a bit of money to powerful equipment for you or your followers. A garrison has 20-25 followers and has about 25-30 missions to choose from per day.

A mission has the following attributes:

1. A level between 90 and 100, inclusive.
2. (for level 100 missions) An equipment level between 615 and 645, in steps of 15.
3. between 1 and 3 slots to send followers with.
4. between 0 and 6 mission threats. There are about 10 categories of threats, the names of which are irrelevant. What is relevant is that a follower can have 1 or 2 abilities that can counter these threats. A mission can have the same threat twice.
5. A zone type where this mission occurs.
6. an enemy type which this mission is fighting against.
7. A duration.

A follower has the following attributes:

1. the race of the follower.
2. A level between 90 and 100, inclusive. followers of equal or higher level contribute more to mission success. A follower that is one level beneath the level of the mission is less effective, but still has an effect. A follower 2 or more levels below the level of the mission does not have an influence on the mission success and cannot counter any threats.
3. (Starting at level 100) An equipment level between 600 and 655, inclusive. Like normal level, followers of equal or higher equipment level are more effective.
4. 1 or 2 abilities that are counters for mission threats. A countered threat increases the chance at success. if all threats are countered with followers of equal of higher level, a mission has a 100% chance of success. A follower can have 2 abilities that counter the same threat.
5. 1, 2 or 3 traits that can give minor chance of success bonuses in specific mission conditions. These don't give as much bonus chance as a full counter, but are useful to optimize for. A trait can counter a zone, a duration or an enemy type. They can also give a bonus for having a specific type of follower on the same mission, or even give an always-on chance of success bonus.

What I understand from some brief chatting with Gamedev.SE, this is basically the Bin Packing problem, with the missions being the packages and the followers being the bins. However, in this case, the bins can combine and are different sizes.

The algorithm I'm looking for aims to do the following in the least amount of time:

1. Maximize the amount of missions with 100% chance of success;
2. Maximize the individual chance of success of each mission that doesn't have 100% chance;

I could probably bruteforce it, but I'm hoping for a somewhat more sophisticated solution.

What algorithm should I use for this?

Answer 1

The thing about these sorts of problems is the solution doesn't have to be perfect. Often the difference between a reasonable heuristic and the optimal solution is very minimal.

So just start out with a greedy algorithm. Sort the missions by best payoff first, and assign the best possible set of followers to the first mission, then the best possible set of remaining followers to the second mission, and so on. By "best" I mean neither overmatched nor undermatched. This is basically how most players would make the assignments manually.

Then backtrack and assign the second best set to the first mission and see if that improves the overall score, then the second best set to the second mission, and so on. Then the second best set to different combinations of two missions, then three missions, and so on. Then repeat with the third best set. Basically a breadth-first search of possible assignments.

What you should find is that after only a few layers deep in the search tree, the improvements start to get smaller and smaller. You cut it off after exceeding a certain threshold in absolute score, after falling below a certain threshold in difference in score between iterations, or after a certain time limit.