Menu
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?
856
We first present an integer formulation for this knapsack problem, so couple constraints related with load balance, vertical (cargo) stability and fragility of the items also called load bearing.
The space complexity is O ( n ) O(n) O(n). This space will be used to store the recursion stack. Since our recursive algorithm works in a depth-first fashion, which means, we can't have more than 'n' recursive calls on the call stack at any time.
0-1 Knapsack cannot be solved by Greedy approach. Greedy approach does not ensure an optimal solution. In many instances, Greedy approach may give an optimal solution.
In this problem, we are given a set of items having different weights and values. We have to find the optimal solution considering all the given items. There are three types of knapsack problems : 0-1 Knapsack, Fractional Knapsack and Unbounded Knapsack. In this article, we will discuss 0-1 Knapsack in detail.
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.
76
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
