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

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');