Multidimensional multiple-choice knapsack problem: find a feasible solution
- by Onheiron
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
R1 R2 R3
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[30] 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:
R1 R2 R3
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?
