01 Knapsack specialization

Question

Excuse me if this has been answered already, but I don't have a deep knowledge of algorithms and don't always notice the subtleties between different specializations of the algorithms. I have (what I think is) a slight variant of the 01-Knapsack problem. I have a knapsack that has max weight W, and there are N items to choose from that have a weight w and value v. What I want to do is maximize the total value, V, without going over W.

Classic Knapsack.

Here's the twist: Of the items, I need to make sure that I have certain amounts (not up-to, but exact amounts) taken from different categories.

So lets assume that we have categories

• F - Food items
• T - Toys
• C - Clothes
• M - Miscellaneous (F, T, or C)

I'm going on a 2 day trip, so I need to take 2 Food items, 1 toy to amuse the kid, and 2 items of clothes. And as a kicker, I can take one additional item that is either a F, T OR C. Note that every item is unique and can be included only once.

From all of algos I've found, it seems like it's a hybrid of the 01 (unique items) and the bounded variant, though in the classic bounded knapsack we are binding the number of times we can include a particular item vs a particular category

If someone could point me to the right algorithm that'd be greatly appreciated. Bonus points for code in a "normal" language, and extra points if the implementation allows me to view the top n-number best results (you know, in case the optimal solution includes the toy that I just REALY can't stand or has 2 outfits that clash with each other).

EDIT: Note that I want to be able to go on longer trips eventually, so I'm looking at taking 8-10 items total and the categories can have up to 250 or so items (that kid has way too many toys). I can do some optimizations to reduce some of the items in each category (I'm really not going to take the ugly hawaiian shirt), but I can't reduce it enough to make a straight brute force implementation feasible.

Answer 1

One possible ILP/LP formulation (the most obvious one, but there's never just one formulation), could be: (not tested)

maximize sum(v[i] * x[i])
subject to:
0 <= x[i] <= 1        // can take every item at most once
sum(w[i] * x[i]) <= W // don't go over the weight limit
F <= sum(f[i] * x[i]) <= F + 1 // take F or F+1 food items
T <= sum(t[i] * x[i]) <= T + 1 // take T or T+1 toys
C <= sum(c[i] * x[i]) <= C + 1 // take C or C+1 clothes
sum(x[i]) == F + T + C + M     // take exactly the right number of items

Where v[i] are values, w[i] are weights, f[i] are the "foodness" of items, t[i] are the "toyness" and by now you know what c[i] will be. Items that fall into more than one category count double or triple (ie if you take an edible toy, it will count towards the toys and towards the food items), which can be avoided by putting in multiple copies of that item, one for each of its categories, where the copies are in only one category each.

But now the real question, how can it be solved? That's still an area of active research, but here's an idea that should work well in this case.

With branch and bound. Bound using the linear relaxation (solve the above problem with linear programming, allowing the decision variables x[i] to be fractions), which should, for this problem, give a pretty decent bound (and admissible, it will always give a solution with an objective value that is at least as high as if you had solved an ILP problem). Branch on a variable that is not an integer.

Answer 2

You may be able to simply brute force all options.

Here is some example Python code:

from itertools import combinations
F=['apple','banana','clementine']
T=['compass','telephone']
C=['socks','gloves','hat']
weights={'apple':1,'banana':2,'clementine':3,'compass':4,'telephone':5,
       'socks':6,'gloves':7,'hat':8}
values={'apple':10,'banana':9,'clementine':8,'compass':7,'telephone':6,
       'socks':5,'gloves':4,'hat':3}
choices=[]
W=45  # Maximum allowed weight
n=5   # Number of choices to display
for M in range(3):  # M represents which category gets an extra item
    num_food = 3 if M==0 else 2
    num_toys = 2 if M==1 else 1
    num_clothes = 3 if M==2 else 2
    for food_to_take in combinations(F,num_food):
        for toys_to_take in combinations(T,num_toys):
            for clothes_to_take in combinations(C,num_clothes):
                things_to_take = food_to_take+toys_to_take+clothes_to_take
                weight = sum(weights[a] for a in things_to_take)
                value = sum(values[a] for a in things_to_take)
                if weight<=W:
                    choices.append([value,weight,things_to_take])
for value,weight,things_to_take in sorted(choices,reverse=True)[:n]:
    print value,weight,things_to_take

prints

43 23 ('apple', 'banana', 'clementine', 'compass', 'socks', 'gloves')
42 24 ('apple', 'banana', 'clementine', 'telephone', 'socks', 'gloves')
42 24 ('apple', 'banana', 'clementine', 'compass', 'socks', 'hat')
41 25 ('apple', 'banana', 'compass', 'telephone', 'socks', 'gloves')
41 25 ('apple', 'banana', 'clementine', 'telephone', 'socks', 'hat')

Answer 3

I think an approach based on Simulated Annealing could work well; SA has been widely applied to KPs, and it's simple to add extra constraints to the solution space. The basic strategy would be as follows:

1. Start with an initial admissible solution consisting of the requisite number of lowest-weight items in each category.
2. In each round, hypothesize replacing one item in a particular category with another item in that category.
3. If the hypothesized candidate solution is not admissible, go to 6.
4. Calculate an acceptance probability for the candidate solution based on its total value relative to the total value of the current solution, and on the annealing schedule.
5. Accept the candidate solution with the calculated probability. If it is accepted, it replaces the current solution; if it is not accepted, the current solution is unchanged.
6. If the total number of annealing rounds has been reached, exit. Otherwise, advance the annealing schedule and go to 2.

For problems that are not especially poorly conditioned, SA does quite well on knapsack problems, so I think it's likely to be fine for your use case. Introductory material on SA, and on annealing schedules and calculating acceptance probabilities, is widely available on the web.

Answer 4

Use genetic algorithm to find an good solution in reasonable time by doing following:-

1. reserve slots in chromosomes for numbers required for each type. For example :-

   Food : milk,apple Toys : etc.. ......

2. Start with valid solution like minimum weights of all types.

3. Try changing values of the items and check if its valid . Find crossover between them such like exchanging there types .

4. Evaluate the best chromosome with max value.

5. Do this till the best chromosome remains the same for fixed no of iterations.