PROBLEM - The algorithm below loops through an array of objects and assigns the objects to three subsets such that the sum of each subset is very close(greedy algorithm). If you run the code, you will notice that in the first subset p:11 appears twice and in third subset p:10 appears twice. I don't want to have p value appear in the same array more than once.
QUESTION - How can I make sure in the algorithm that the value of p does not appear in the same subset array more than once as the objects are being distributed to the subset arrays while making sure the sum of each subset array is still the same?
let list = [
{p:2, size:50},{p:4, size:50},{p:5,size:25},
{p:6, size:167},{p:6, size:167},{p:7, size:50},
{p:8, size:25},{p:8, size:50},{p:10, size:75},
{p:10, size:75},{p:11, size:25},{p:11, size:50},
{p:12, size:25},{p:13, size:50},{p:14,size:25}
]
function balance_load(power_load_array, number_of_phases) {
const sorted = power_load_array.sort((a, b) => b.size - a.size); // sort descending
const output = [...Array(number_of_phases)].map((x) => {
return {
sum: 0,
elements: [],
};
});
for (const item of sorted) {
const chosen_subset = output.sort((a, b) => a.sum - b.sum)[0];
chosen_subset.elements.push({p:item.p, size:item.size});
chosen_subset.sum += item.size;
}
return output
}
let p = balance_load(list,3)
console.log(p)This can be solved as an integer linear optimization problem with one continuous variable, t, and one variable for each combination of element of list, i and group, j:
1 if element i of list is assigned to group j, else it equals 0.We are given the following coefficients.
ci: cost of element i of list (list[i][:size])
pi: value of p for element i of list (list[i][:p])
S : set of unique values list[i][:p] that are shared by two or more elements of list.
U(s) : set of elements i of list for which list[i][:p] == s, for each s in S
The formulation is as follows.
(1) min t
subject to:
(2) t >= ∑i xijcij for each j
(3) ∑j xij = 1 for each i
(4) ∑U(s) xij <= 1 for each j and s in S
(5) xij equals 0 or 1 for all i,j pairs
list to be assigned to exactly one grouplist that have the same value of list[:p] are assigned to the same group.