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?