5

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!

  • Can points have same weights? – sventevit Jul 12 '13 at 21:00
  • Yeah they could have the same weights – CodeMonkey42 Jul 12 '13 at 21:23
  • To clarify: What you say is you have a sequence of numbers (the weights of the consecutive points), and the goal is to apply up to k-1 cuts to that sequence, such that the variance within the resulting segments is minimized, right? – tobias_k Jul 13 '13 at 13:03
  • Also - should all bins have equal number of points? Do the bins have a predefined count (or sum) of points or should they just be as equal as possible? – sventevit Jul 14 '13 at 11:09
  • All bins don't have to have the same number of points. The goal is just to have the minimum deviation (total error) from all choices of bin estimates and points in those bins. – CodeMonkey42 Jul 15 '13 at 15:49
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

0

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(n2k). 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).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.