Q:

0-1 Knapsack w/ partitioning constraints

I have a problem that on the surface looks like 0-1 knapsack.  I have a set of possible "candidates" that can be choosen (or not), each candidate has a "weight" (cost) and a potential "value".  Were this the entire problem, I'd use a DP approach and be done with it.  But here's the curveball:  There are "partitioning constraints" on the possible candidates that can be in the final solution.
What I mean is that the candidate space is split into discrete equivalence classes.  For my particular problem there are about 300 candidates and 12 possible equivalence classes.  There are "buisness rules" that say I can only have up to say 3 candidates from class C1 and 6 candidates from C2, etc.  
This constraint suggests a graph-search type approach using branch-and-bound techniques or some other form of pruning, however I am somewhat stumped as to how to began since I am only familiar with the DP solution to 0-1 Knapsack.  What techniques/approaches might be suitable for this problem?  I also thought of maybe using a constraint programming library but am not sure if it would be able to find a solution?

A:

You could try an Integer Linear Programming solver, where there is a binary variable for choosing each candidate. The constraints are easily expressed as linear inequations. With 300 variables, a solver should not have much trouble solving it.
The easiest way would probably be to write your problem in a text format such as the CPLEX LP format, and then use a solver like Coin CBC or GLPK.

