Parabolic knapsack

I cooked up a solution in JavaScript using processing.js and HTML5 canvas.

This project should be a good starting point if you want to create your own solution. I added two algorithms. One that sorts the input blocks from largest to smallest and another that shuffles the list randomly. Each item is then attempted to be placed in the bucket starting from the bottom (smallest bucket) and moving up until it has enough space to fit.

Depending on the type of input the sort algorithm can give good results in O(n^2). Here's an example of the sorted output.

Here's the insert in order algorithm.

function solve(buckets, input) {
  var buckets_length = buckets.length,
      results = [];

  for (var b = 0; b < buckets_length; b++) {
    results[b] = [];
  }

  input.sort(function(a, b) {return b - a});

  input.forEach(function(blockSize) {
    var b = buckets_length - 1;
    while (b > 0) {
      if (blockSize <= buckets[b]) {
        results[b].push(blockSize);
        buckets[b] -= blockSize;
        break;
      }
      b--;
    }
  });

  return results;
}

Project on github - https://github.com/gradbot/Parabolic-Knapsack

It's a public repo so feel free to branch and add other algorithms. I'll probably add more in the future as it's an interesting problem.

Simplifying

First I want to simplify the problem, to do that:

• I switch the axes and add them to each other, this results in x2 growth
• I assume it is parabola on a closed interval [a, b], where a = 0 and for this example b = 3

Lets say you are given b (second part of interval) and w (width of a segment), then you can find total number of segments by n=Floor[b/w]. In this case there exists a trivial case to maximize Riemann sum and function to get i'th segment height is: f(b-(b*i)/(n+1))). Actually it is an assumption and I'm not 100% sure.

Max'ed example for 17 segments on closed interval [0, 3] for function Sqrt[x] real values:

And the segment heights function in this case is Re[Sqrt[3-3*Range[1,17]/18]], and values are:

• Exact form:

{Sqrt[17/6], 2 Sqrt[2/3], Sqrt[5/2], Sqrt[7/3], Sqrt[13/6], Sqrt[2], Sqrt[11/6], Sqrt[5/3], Sqrt[3/2], 2/Sqrt[3], Sqrt[7/6], 1, Sqrt[5/6], Sqrt[2/3], 1/Sqrt[2], 1/Sqrt[3], 1/Sqrt[6]}

• Approximated form:

{1.6832508230603465, 1.632993161855452, 1.5811388300841898, 1.5275252316519468, 1.4719601443879744, 1.4142135623730951, 1.35400640077266, 1.2909944487358056, 1.224744871391589, 1.1547005383792517, 1.0801234497346435, 1, 0.9128709291752769, 0.816496580927726, 0.7071067811865475, 0.5773502691896258, 0.4082482904638631}

What you have archived is a Bin-Packing problem, with partially filled bin.

Finding b

If b is unknown or our task is to find smallest possible b under what all sticks form the initial bunch fit. Then we can limit at least b values to:

1. lower limit : if sum of segment heights = sum of stick heights
2. upper limit : number of segments = number of sticks longest stick < longest segment height

One of the simplest way to find b is to take a pivot at (higher limit-lower limit)/2 find if solution exists. Then it becomes new higher or lower limit and you repeat the process until required precision is met.

When you are looking for b you do not need exact result, but suboptimal and it would be much faster if you use efficient algorithm to find relatively close pivot point to actual b.

For example:

• sort the stick by length: largest to smallest
• start 'putting largest items' into first bin thy fit

This is equivalent to having multiple knapsacks (assuming these blocks are the same 'height', this means there's one knapsack for each 'line'), and is thus an instance of the bin packing problem.

See http://en.wikipedia.org/wiki/Bin_packing

How can I stack these sticks within the parabola such that I am minimizing the (vertical) space it uses as much as possible?

Just deal with it like any other Bin Packing problem. I'd throw meta-heuristics on it (such as tabu search, simulated annealing, ...) since those algorithms aren't problem specific.

For example, if I'd start from my Cloud Balance problem (= a form of Bin Packing) in Drools Planner. If all the sticks have the same height and there's no vertical space between 2 sticks on top of each other, there's not much I'd have to change:

• Rename Computer to ParabolicRow. Remove it's properties (cpu, memory, bandwith). Give it a unique level (where 0 is the lowest row). Create a number of ParabolicRows.
• Rename Process to Stick
• Rename ProcessAssignement to StickAssignment
• Rewrite the hard constraints so it checks if there's enough room for the sum of all Sticks assigned to a ParabolicRow.
• Rewrite the soft constraints to minimize the highest level of all ParabolicRows.

I'm very sure it is equivalent to bin-packing:

informal reduction

Be x the width of the widest row, make the bins 2x big and create for every row a placeholder element which is 2x-rowWidth big. So two placeholder elements cannot be packed into one bin.

To reduce bin-packing on parabolic knapsack you just create placeholder elements for all rows that are bigger than the needed binsize with size width-binsize. Furthermore add placeholders for all rows that are smaller than binsize which fill the whole row.

This would obviously mean your problem is NP-hard.

For other ideas look here maybe: http://en.wikipedia.org/wiki/Cutting_stock_problem