Partitioning weighted elements with a restriction on total partition weight

Question

Given a large array of positive integer "weights", e.g. [ 2145, 8371, 125, 10565, ... ], and a positive integer "weight limit", e.g. 15000, I want to partition the weights into one or more smaller arrays, with the following criteria:

1. I want to minimize the number of partitions.
2. No single partition can add up to more than the weight limit. (Note that no single weight will exceed this limit.)

I suspect this problem has a high complexity class. As answers, I'm interested in:

1. Optimal solutions
2. Not-quite-optimal, but fast-running (approximate) solutions

Current non-optimal approach: (Basic greedy algorithm; JavaScript)

function minimizePartitions(weights, weightLimit) {
  let currentPartition = [];
  let currentSum = 0;
  let partitions = [ currentPartition ];
  
  for (let weight of weights) {
    if (currentSum + weight > weightLimit) {
      currentPartition = [];
      currentSum = 0;
      partitions.push(currentPartition);
    }
    
    currentPartition.push(weight);
    currentSum += weight;
  }
  
  return partitions;
}

let weights = [3242, 987, 1222, 7299, 400, 10542, 10678, 513, 3977];
console.log(minimizePartitions(weights, 15000));

Answer 1

This is a bin-packing problem and is known to be NP-hard.

For a quick approximation I would suggest sorting from largest to smallest, and then putting each element in the bin that it fits in which is closest to full.

Answer 2

An approach to a pretty fast but quite approximage solution could be the following.

Let's sort items by weight.

With the maximum partition weight W, the lower bound of the number of partitions is P = sum(weights of all pieces) / W.

Let's make as many partitions initially, and distribute items from heaviest to lightest, trying to put in each partition the heaviest item it can still fit.

If some items remain (they would unless we found a perfect combination), put them into another partition (or even several), by running the same algorithm. Note that such overflow partition(s) will have the lightest-weight items.

The above runs in linear time (though the preceding sorting items by weight is log-linear).

Depending on the distribution of weights, and on how tight our limits are, we can consider optimizations.

If our number P is slightly above the closest integer (e.g. 3.005), and we have P + 1 partitions, we can't hope to reduce their number, and can stop.

If P is somehow below the closest integer (e.g. 2.77), and we have P + 2 partitions, we can hope to push items from one overflow partition inside the vacant spaces in other partitions.

To do so, we could swap elements between partitions, trying to maximize the vacant space in one of them (and minimize in another), and put some item from an overflow partition into that vacant space. The swapping step is required, else an item would just fit into that partition on the first run, and won't go to the overflow partition. If no swapping that would make a large enough vacant space is possible any more, this optimization phase should stop.

This part is highly non-linear (won't analyze it in this crude description). It can likely be limited by run time (don't try to optimize for longer than 1s) and depends on the distribution of sizes. With some luck, this step should be able to eliminate a loose overflow partition often enough.

Hope this helps.

Answer 3

Optimal

Here is an implementation of a brute force approach that generates all possible partitions of the weights where the partition satisfies the constraint, then keeps track of the ideal solution as it iterates the partitions.

It always produces an ideal solution, but testing in Node.js, it takes about 50 seconds to run on my machine for just this array of 9 values.

So fair warning, running this may crash your browser.

// adapted from https://stackoverflow.com/a/31145957/1541563
function nextPermutation (array, compare) {
  let i = array.length - 1;

  while (i > 0 && compare(array[i - 1], array[i]) >= 0) {
    i--;
  }

  if (i === 0) return false;

  let j = array.length - 1;

  while (compare(array[j], array[i - 1]) <= 0) {
    j--;
  }

  [array[i - 1], array[j]] = [array[j], array[i - 1]];

  let k = array.length - 1;

  while (i < k) {
    [array[i], array[k]] = [array[k], array[i]];
    i++;
    k--;
  }

  return true;
}

function * permutations (array, compare) {
  array.sort(compare);

  do {
    yield [...array];
  } while (nextPermutation(array, compare));
}

function * partitions (array, predicate) {
  if (predicate(array)) yield [array];

  const end = array.length - 1;

  for (let i = 1; i < end; i++) {
    for (const a of partitions(array.slice(0, i), predicate)) {
      for (const b of partitions(array.slice(i), predicate)) {
        yield [...a, ...b];
      }
    }
  }
}

function * partitionsOfPermutations (array, predicate, compare) {
  for (const permutation of permutations(array, compare)) {
    yield * partitions(permutation, predicate);
  }
}

function idealPartition (array, predicate, comparePartitions, compareValues) {
  const iterator = partitionsOfPermutations(array, predicate, compareValues);
  let ideal = iterator.next().value;

  for (const partition of iterator) {
    if (comparePartitions(ideal, partition) > 0) {
      ideal = partition;
    }
  }

  return ideal;
}

const weights = [3242, 987, 1222, 7299, 400, 10542, 10678, 513, 3977];

const limit = 15000;

function constraint (weights) {
  return weights.reduce(
    (sum, weight) => sum + weight,
    0
  ) <= limit;
}

function minPartition (a, b) {
  return a.length - b.length;
}

function minValue (a, b) {
  return a - b;
}

const solution = idealPartition(
  weights,
  constraint,
  minPartition,
  minValue
);

console.log(solution);
console.log((performance.now() / 1000).toFixed(2), 'seconds');

If there is no solution given the constraint, the return value will be undefined. In this case it returns:

[ [ 400, 513, 987, 1222, 3242, 7299 ],
  [ 10542 ],
  [ 3977, 10678 ] ]

Using dynamic programming, it's definitely possible to improve on this brute force algorithm. I'll leave that as an exercise to the reader, though.

The nice thing about this approach is it's general enough to work for a large class of ideal partition problems.

Non-optimal approximation

If you specify a cutoff criteria for the ideal partition, the program can terminate early if it's found a partition that is "good enough". This is quite fast depending on the chosen predicate. For this particular input it can return an ideal solution in less than a second:

// adapted from https://stackoverflow.com/a/31145957/1541563
function nextPermutation (array, compare) {
  let i = array.length - 1;

  while (i > 0 && compare(array[i - 1], array[i]) >= 0) {
    i--;
  }

  if (i === 0) return false;

  let j = array.length - 1;

  while (compare(array[j], array[i - 1]) <= 0) {
    j--;
  }

  [array[i - 1], array[j]] = [array[j], array[i - 1]];

  let k = array.length - 1;

  while (i < k) {
    [array[i], array[k]] = [array[k], array[i]];
    i++;
    k--;
  }

  return true;
}

function * permutations (array, compare) {
  array.sort(compare);

  do {
    yield [...array];
  } while (nextPermutation(array, compare));
}

function * partitions (array, predicate) {
  if (predicate(array)) yield [array];

  const end = array.length - 1;

  for (let i = 1; i < end; i++) {
    for (const a of partitions(array.slice(0, i), predicate)) {
      for (const b of partitions(array.slice(i), predicate)) {
        yield [...a, ...b];
      }
    }
  }
}

function * partitionsOfPermutations (array, predicate, compare) {
  for (const permutation of permutations(array, compare)) {
    yield * partitions(permutation, predicate);
  }
}

function idealPartition (array, predicate, comparePartitions, compareValues, cutoff) {
  const iterator = partitionsOfPermutations(array, predicate, compareValues);
  let ideal = iterator.next().value;

  for (const partition of iterator) {
    if (comparePartitions(ideal, partition) > 0) {
      if (cutoff(ideal = partition)) return ideal;
    }
  }

  return ideal;
}

const weights = [3242, 987, 1222, 7299, 400, 10542, 10678, 513, 3977];

const limit = 15000;

function constraint (weights) {
  return weights.reduce(
    (sum, weight) => sum + weight,
    0
  ) <= limit;
}

function minPartition (a, b) {
  return a.length - b.length;
}

function minValue (a, b) {
  return a - b;
}

// we already know the solution to be size 3
const average = Math.ceil(
  weights.reduce(
    (sum, weight) => sum + weight,
    0
  ) / limit
);

function isSolution (partition) {
  return partition.length === average;
}

const solution = idealPartition(
  weights,
  constraint,
  minPartition,
  minValue,
  isSolution
);

console.log(solution);
console.log((performance.now() / 1000).toFixed(2), 'seconds');