Bin sorting problem - Please help categorize

Question

I have a problem I am developing a solution for and currently I solve it with a brute force solution that checks all possibilities. It works for small numbers of bins but I'd like to work with a reasonable speed for increasing numbers, however the algorithm I use (brute force) increases in computing time in a factorial manner related to the number of bins. In other words it gets way too slow pretty quickly after about 6 or 7 bins. I'd like to classify the problem to see if it is NP-Complete, NP-Hard or other so I know where to look in attempting to optimize.

The basic problem is this.

You have a number of points n and you have weights for these points. The points also have an ordering such that points in a bin must be consecutive. You must place these into a total of a maximum of k bins. The bins contain an estimate for the set of points placed in it and the total error of the absolute value of difference in the points and the estimate must be minimized. The goal is to find how to place these points in the bins to have the minimal total error.

Thanks!

Answer 1

Just an idea: randomly swap items in bins, something like this:

using System;
using System.Linq;
using System.Collections.Generic;

namespace BinsGenetic
{
    class Program
    {
        private const int NumberOfBins = 10;
        private const int NumberOfPoints = 100000;
        private const int MinimalPoint = 1;
        private const int MaximalPoint = 1000;
        private const int NumberOfSwaps = 10000;

        static void Main()
        {
            // Generate empty bins.
            var bins = new List<Bin>();
            for (int i = 0; i < NumberOfBins; i++)
            {
                bins.Add(new Bin(i + 1));
            }

            // Generate 100 points with weight from 1 to 10.
            var points = new List<int>();
            var rnd = new Random();
            for (int i = 0; i < NumberOfPoints; i++)
            {
                points.Add(rnd.Next(MinimalPoint, MaximalPoint));
            }

            // Insert points into bins by random order.
            int c = 0;
            foreach (var point in points.OrderBy(p => p))
            {
                bins[c].Add(point);
                c++;
                if (c % NumberOfBins == 0) c = 0;
            }

            Console.WriteLine("Initial:");
            Test(bins);

            // Get max and min bin.
            for (int i = 0; i < NumberOfSwaps; i++)
            {
                var b1 = bins[rnd.Next(0, NumberOfBins)];
                var b2 = bins[rnd.Next(0, NumberOfBins)];

                var p1 = b1.Points[rnd.Next(0, b1.Points.Count)];
                var p2 = b2.Points[rnd.Next(0, b2.Points.Count)];

                var initialSumBin1 = b1.Points.Sum(p => p);
                var initialSumBin2 = b2.Points.Sum(p => p);
                var initialDiff = Math.Abs(initialSumBin1 - initialSumBin2);

                b1.Add(p2);
                b2.Remove(p2);
                b2.Add(p1);
                b1.Remove(p1);

                var finalSumBin1 = b1.Points.Sum(p => p);
                var finalSumBin2 = b2.Points.Sum(p => p);
                var finalDiff = Math.Abs(finalSumBin1 - finalSumBin2);

                if (finalDiff < initialDiff)
                {
                    Console.WriteLine("Optimized {0}:", i);
                    Test(bins);
                }
                else
                {
                    b1.Add(p1);
                    b2.Remove(p1);
                    b2.Add(p2);
                    b1.Remove(p2);
                }
            }

            Console.WriteLine("Final:");
            Test(bins);

            Console.ReadKey();
        }

        private static void Test(List<Bin> bins)
        {
            // Test.
            for (int i = 0; i < bins.Count; i++)
            {
                Console.Write("Bin {0}, Count: {1}, Sum:{2}, Points:", i + 1, bins[i].Points.Count, bins[i].Points.Sum(p => p));
                //foreach (var point in bins[i].Points.OrderByDescending(p => p))
                //{
                //    Console.Write("{0} ", point);
                //}
                Console.WriteLine();
            }
            Console.WriteLine();
        }
    }

    class Bin
    {
        public readonly List<int> Points;
        public int Id { get; private set; }

        public Bin(int id)
        {
            Points = new List<int>();
            Id = id;
        }

        public void Add(int point)
        {
            Points.Add(point);
        }

        public void Remove(int point)
        {
            Points.Remove(point);
        }
    }
}

But I don't have an idea how to set NumberOfSwaps const. In this example I set it by testing... Of course you can't be sure that you got the optimal result.

But for more advanced/academic/production ready algorithms you can start your research here:Bin packing problem

Answer 2

This problem can be solved exactly in polynomial time by using dynamic programming. Let E[i,b] be the smallest possible error on bins b, b+1, ..., k when those bins contain items i, i+1, ..., n and no others. Observe that we wish to calculate E[1,1], which we'll do by tabulating all values E[i,b] for 1 ≤ i ≤ n and 1 ≤ b ≤ k.

I'm going to write c[b] for the capacity of the b'th bin, w[i] for the weight of the i'th item and w[i,j] for w[i] + ... + w[j].

First, observe that, for any i, E[i,k] = |w[i,n] - c[k]|, because that is the only possible error from putting all of items i through n in bin k. To calculate E[i,b] for some b < k, observe that we either put items i, ..., j (for some j ≥ i) in bin b and items j+1, ..., n in bins b+1, ..., k; or we put all of items i, ..., n in bins b+1, ..., k. Therefore,

E[i,b] = min ({E[i,b+1]} ∪ {|w[i,j] - c[b]| + E[j+1,b+1] : i < j ≤ n}

Since each E[i,b] only depends on values E[i',b'] for i' > i and b' > b, we can just compute them in descending order of b and i. So, we can compute E[1,1] in time something like O(n²k). Since the input contains the n weights and k costs, the input has length at least nk, so this is a true polynomial time algorithm (as distinct from the pseudopolynomial algorithms you usually get for bin packing problems).