# Multidimensional multiple-choice knapsack problem: find a feasible solution

My assignment is to use local search heuristics to solve the Multidimensional multiple-choice knapsack problem, but to do so I first need to find a feasible solution to start with.

Here is an example problem with what I tried so far.

## Problem

``````           L1  L2  L3

RESOUCES : 8   8   8

GROUPS:

G1:

11.0    3    2    2
12.0    1    1    3

G2:

20.0    1    1    3
5.0     2    3    2

G3:

10.0    2    2    3
30.0    1    1    3
``````

## Sorting strategies

To find a starting feasible solution for my local search I decided to ignore maximization of gains and just try to fit the resources requirements.

I decided to sort the choices (strategies) in each group by comparing their "distance" from the multidimensional space origin, thus calculating `SQRT(R1^2 + R2^2 + ... + RN^2)`. I felt like this was a keen solution as it somehow privileged those choices with resouce usages closer to each other (e.g. R1:2 R2:2 R3:2 < R1:1 R2:2 R3:3) even if the total sum is the same.

Doing so and selecting the best choice from each group proved sufficent to find a feasible solution for many different benchmark problems, but of course I knew it was just luck. So I came up with the problem presented above which sorts like this:

``````           L1  L2  L3

RESOUCES : 8   8   8

GROUPS:

G1:

12.0    1    1    3 < select this
11.0    3    2    2

G2:

20.0    1    1    3 < select this
5.0     2    3    2

G3:

30.0    1    1    3 < select this
10.0    2    2    3
``````

And it is not feasible because the resources consmption is R1:3, R2:3, R3:9.

The easy solution is to pick one of the second best choices in group 1 or 2, so I'll need some kind of iteration (local search[?]) to find the starting feasible solution for my local search solution.

Here are the options I came up with

Option 1: iterate choices

I tried to find a way to iterate all the choices with a specific order, something like

``````G1   G2   G3
1    1    1
2    1    1
1    2    1
1    1    2
2    2    1
...
``````

believeng that feasible solutions won't be that far away from the unfeasible one I start with and thus the number of iterations will keep quite low.

Does this make any sense? If yes, how can I iterate the choices (grouped combinations) of each group keeping "as near as possibile" to the previous iteration?

Option 2: Change the comparation term

I tried to think how to find a better variable to sort the choices on. I thought at a measure of how "precious" a resource is based on supply and demand, so that an higer demand of a more precious resource will push you down the list, but this didn't help at all.

Also I thought there probably isn't gonna be such a comparsion variable which assures me a feasible solution at first strike.

I there such a variable? If not, is there a better sorting criteria anyways?

Option 3: implement any known sub-optimal fast solving algorithm

Unfortunately I could not find any of such algorithms online. Any suggestion?

## EDIT

NOTE: I updated the previous description using labels L1 L2 L3 for the problem resource limits in place of R1 R2 R3 which now indicate the resource requirements of each strategy (choice)

Fallowing the input by @J Trana, I decided to go and try a genetic algorithm for the problem setup.

This seemed quite fitting to the problem structure as each Group is a Gene, each Solution is a Chromosome and each Strategy is an Allele.

I also modified the distance expression to fit better with heterogeneous resource limits, so now the distance is : `SUM(Rn/Ln)` which should give a lower distance (i.e. higher priority) to those strategies with lower resource requirement portions.

Since this part is intended only for solving initialization, I chose the fallowing genetic functions:

## Fitness

``````// if solution is feasible, that's just enough, it has the greatest fitness possible
if(solution.isFeasibleInProblem()) return Integer.MAX_VALUE;

ArrayList<Integer> consumptions = new ArrayList<Integer>();

for(Integer limit : problem.resourceLimits){
}

// add the resources consumptions from each group
for(Group g : genes){
for(int i = 0; i < g.currentSelectedSolution.resourceRequirements.size(); i++){
consumptions.set(i, consumptions.get(i) + g.currentSelectedSolution.resourceRequirements.get(i));
}
}

ArrayList<Double> subFitnesses = new ArrayList<Double>();

// each subFitness is the ratio between the total limit and the actual consumption
// this way if the consumption is < limit subFitness is greater than 1 (rises the fitness), else it is less than 1 and lowers the fitness
for(int j = 0; j < consumptions.size(); j++){
double subFitness = problem.limits.get(j) / consumptions.get(j);
}

double fitness = 1;

for(Double sF : subFitnesses){
fitness *= sF;
}

return fitness;
``````

So resource requirements lesser than the limit rise the fitness, where requirements greater than the limit lower the fitness.

## Mutation

For the mutation function I found that feasible solutions contain strategies with smaller distance and considering solutions far down in the ordered distance list slows the evolution because most of the time those mutations have negative effects.

``````public void mutate(int strategyIndex, double mutationIntensity){

// if there's no choice, don't mutate
if(this.strategies.size() <= 1) return;

... here I'd need something that keeps in the first positions of the list
but eventually, with higher mutation intensities, goes to greater indexes...

selectStrategy(newStrategyIndex);

}
``````

The above solution works very well for most of the benchmarks, but there are 2 of them, having a lot of choices per group and a lot of resources per choice, that simply won't find a feasible solution.

How could I implement the mutation algorithm so that those 2 benchmarks convert to a feasible solution? Is there any improvement I can put in my fitness function or in the strategy ordering to speed up the solving path?

• Have you tried any of the more "black box" types of solution finders? If I were given this assignment, I would probably go to genetic algorithms first. Not everything is a good candidate for that and indeed classical solvers are often recommended first but that is where I would start for sure. The funny thing is that depending on your local search heuristics, genetic algorithms may get you some of that too depending on the design of your fitness function... – J Trana Jun 8 '14 at 2:48
• @J Trana thanks, I edited the question with what I tried, can you suggest me a valid mutation function? – Onheiron Jun 11 '14 at 11:16
• Simulated Annealing may be of some assistance here in addition to a genetic algorithm although I think you are interested in a heuristic that can find a provable search space. – Mushy Jun 11 '14 at 16:25
• Hey, just checked back after a couple days. Good work so far, glad to see you've got it partially working. As for mutation, I think you're on the right path more or less, but one thing I wasn't sure if you skipped or didn't show was how "badly" the mutation occurred. I would expect a mutation factor to be a random independent variable that, once crossing a threshold, triggered a change in index. However, if distance in strategy index means anything, you might want to actual jump more than one index if the mutation is "bad". – J Trana Jun 12 '14 at 4:29
• Also, as general notes here, I think some useful stats to post would be population size, number of iterations, and likelihood of mutations. These will help us know how to help. One common thing I've done is left the population size too small or grown impatient on the number of iterations, so I cheat by making the population size too small, decreasing the mutation factor too much, or being too elitist in my preservation strategies. (Good in the right scenarios, though) These can lead to too much inbreeding or too rapid of selection of genes, causing poor or non-existent local optima. – J Trana Jun 12 '14 at 4:35