Is this NP-Complete? If so, knapsack, MIS, set-filling or scheduling?

Question

I've got a "gut-feeling" that the problem I'm facing in my application is NP-complete, but I'm after help classifying it.

The problem

• We have a bag with n heterogeneous slots
• We can either put an item (with an associated value) in each slot, or leave it empty. A slot may contain at most one item.
• Since the slots are heterogeneous, an item for slot #2 cannot go in slot #3
• We have a finite set of slot-filling actions
• Each action may be invoked at most once
• Invoking a given action will fill some (1-n) of the slots with a fixed value (specific to the action), but only if all requested slots are available (otherwise the action cannot be invoked) i.e. all requested slots or none.

How do we determine the set of actions to invoke to maximise the total value in the bag?

An example:

• We have 5 slots, numbered #1-#5
• We have three actions, A1, A2 and A3
• A1 wants to put value $30 in slots #1 through #5
• A2 wants to put $50 in slots #1 & #2
• A3 wants to put $50 in slots #4 & #5

The optimal solution for this example is to invoke actions A2 & A3 (for a total value of $200, leaving slot #3 empty) - rather than invoking A1 (which would fill all slots, but only give a total of $150).

Follow-up question - how should I brute-force this?

Some thoughts:

• We will want to prune off any action A[y] which covers the exact same slots as another action A[x] if the slot value ($) associated with A[y] is less than or equal to that of A[x].

• Other than that, I think evaluating the solution space boils down to iterating through the powerset of all remaining actions

• Of the sets {S1, S2...} in the powerset of all actions, if S2 is a subset of S1 AND all the actions applied successfully for S1 then we can disregard S2 (and all it's subsets!) without evaluating them, since they can never give a better result. In other words, if we can find a set that applies successfully early on, we can disregard all the subsets of it (significantly reducing what we have to test)

Interested to hear of any other optimisations you can think of.

Answer 1

NP-completeness is about decision problems, and yours is an optimization problem. If we change it to feasibility ("does a solution ≥ m exist?") then we can trivially reduce set packing to your problem, and your problem to 0-1 integer linear programming, both of which are known to be NP-complete. Congratulations, you're NP-complete!

I'm not sure which NPO-complete class your problem falls into, though.