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? Commented Jul 12, 2013 at 21:00
• Yeah they could have the same weights Commented Jul 12, 2013 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? Commented Jul 13, 2013 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? Commented Jul 14, 2013 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. Commented Jul 15, 2013 at 15:49

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++)
{
}

// 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++)
{
}

// Insert points into bins by random order.
int c = 0;
foreach (var point in points.OrderBy(p => p))
{
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);

b2.Remove(p2);
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
{
b2.Remove(p1);
b1.Remove(p2);
}
}

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

}

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 int Id { get; private set; }

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

{
}

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.