Optimal combination of N products with M features

Question

I have X number of parts with fixed cost. Each part having N aspects of different value.

For example:

Part 1: cost = 3,
Width = 10,
Length = 12,
Height = 13,
Weight = 12,
Value = sum of four aspects = 47

Part 2: cost 4,
Width = 20,
Length = 15,
Height = 12,
Weight = 10,
Value = sum of above four aspects = 57

Part 3: cost 2,
Width = 9,
Length = 12,
Height = 9,
Weight = 8,
Value = sum of above four aspects = 38

I then have many such different items e.g. 20 items. There's a cap on maximum number of items I can choose at a time e.g. 8 items. I have a cost cap i.e. the sum of cost of chosen items should be with a prescribed limit e.g. 30.

I now have to choose items from this list so that I have maximum value. Another constrain is that, all the aspects should be balanced in the final combination. e.g. final sum of Width, Length, Height, and Weight should be equally distributed. If not equal, at least in a balanced range. i.e. as there are 4 aspects, every aspect should be about 25% +/-5% of the total value.

I tried solving it the Knapsack Problem way but I have more dimensions here.

Answer 1

One way would be through a MILP-model. Here is a simple model implemented in MiniZinc. x are binary variables representing if an item is choosen or not.

int: items = 5;
int: selectedItems = 3;
int: maxCost = 10;

set of int: ITEM = 1..items;

array[ITEM] of int: cost = [3, 4, 2, 1, 1];
array[ITEM] of int: width = [10, 20, 9, 15, 12];
array[ITEM] of int: length = [12, 15, 12, 15, 12];
array[ITEM] of int: height = [13, 12, 9, 15, 12];
array[ITEM] of int: weight = [12, 10, 8, 15, 12];
array[ITEM] of int: value = [width[i] + length[i] + height[i] + weight[i] | i in ITEM];
    
array[ITEM] of var 0..1: x;

% selected items constraint
constraint sum(x) <= selectedItems;

% cost constraint
constraint sum(i in ITEM)(cost[i]*x[i]) <= maxCost;

predicate balanced(array[ITEM] of var int: values) =
    let {var int: value = sum(i in ITEM)(values[i]*x[i])} in
    value >= 0.2*totalValue /\ value <= 0.3*totalValue;

% balance constraints
constraint balanced(width) /\ balanced(length) /\ balanced(height) /\ balanced(weight);

var 1..sum(value): totalValue = sum(i in ITEM)(value[i]*x[i]);

solve maximize totalValue;

output ["totalValue=\(totalValue)\n"] ++
["cost=\(sum(i in ITEM)(cost[i]*x[i]))\n"] ++ 
["x="] ++ [show(x)] ++
["\nratio="] ++ [show_float(5, 2,sum(i in ITEM)(width[i]*x[i]) / totalValue), show_float(5, 2,sum(i in ITEM)(length[i]*x[i]) / totalValue), show_float(5, 2,sum(i in ITEM)(height[i]*x[i]) / totalValue), show_float(5, 2,sum(i in ITEM)(weight[i]*x[i]) / totalValue)] ++
["\nvalue="] ++ [show(value)];

Running (with default Gecode solver) gives:

totalValue=165
cost=6
x=[0, 1, 0, 1, 1]
ratio= 0.28 0.25 0.24 0.22
value=[47, 57, 38, 60, 48]