Advice for a problem

[savavampir]

Hello everybody, my first post here.
I have a problem for witch i don't know where to start from.
Lets imagine a carpenter, and he have a pile of wooden beams with fixed size say 8 meters.
Now he have to cut those:
'x' number of pieces with 'i' length
'y' number of pieces with 'j' length
'z' number of pieces with 'k' length
..etc
and with minimum wastage of "row" material. I don't need solution in code, just some thoughts/pseudo as how would you approach this.
Thanks greatly on your time.

[simeonz]

Do I understand correctly that x, y, z, etc are to be determined, and i, j, k are fixed. I mean, if x, y, z,... were fixed, then the total utilized material would be fixed, and then the waste is fixed (for a given number of beams). If you could specify: the function that needs to be optimized, the constraints that need to be satisfied, and the variables that have to be determined, preferably with expressions, it would make things more clear.

Related, but different problems:
http://en.wikipedia.org/wiki/Knapsack_problem
(does not optimize the waste, but x + y + z)
http://en.wikipedia.org/wiki/Bin_packing_problem
(this would minimize the number of used beams if x, y, z are fixed)

You can use dynamic programming to solve the problem. Then again, this is not saying much lol It's not always the most efficient way. I don't have much time right now, but I'll get back to you.

Regards

[savavampir]

const double fixedLenghtOfRowBeamFromPile = 8.0;

short numPieces0 = x;
double length0 = i;

short numPieces1 = y;
double length1 = j;

short numPieces2 = z;
double length2 = k;
...and so on

Calculate minimum wastage of "row" material.
I have yet to see links you've provided to see if it is related.
Thanks for your time.

EDIT: x,y & z cannot be larger then fixedLenghtOfRowBeamFromPile

[simeonz]

Just to remark. This is a tough (computationally-wise) problem. First, it is not Knapsack problem it appears, because your lengths are not integer.

Just a brief summary on the Knapsack anyways. It computes the problem for smaller beam lengths first and then increases the beam length gradually, solving larger problems in terms of the memorized solutions for the smaller ones. It derives the solution when the beam length reaches the target beam length from the original problem. This method requires lots and lots of memory, but promises decent performance. (Decent is very vague word when used with performance though.)

The reason why this algorithm can not be applied here is that the costs, lengths in your case, are not integral values. Consequently, growing the beam is not possible with unit steps without skipping over valid lengths. The real axis is continuous, and you can't step through real numbers, which disqualifies the Knapsack solution on Wikipedia.

This may be your problem, although I see no solution there: http://en.wikipedia.org/wiki/Cutting_stock_problem

Some details for its complexity class you can find here, but I am not sure if they address your variant exactly: http://cstheory.stackexchange.com/questions/1289/2d-cutting-stock-problem-for-glass-details-mentioned/1338#1338

I have tried to produce algorithm, which you must check independently. I am not sure it is bullet proof. It probably runs in polynomial time in terms of the ratio between the beam length and the piece lengths (the smallest of them or smth), but in exponential time in terms of the types of pieces that you want to support. For two pieces, this algorithm should have linear complexity, for three types of pieces - quadratic, for four - cubic. As a side note, anything above linear complexity is not really useful for large problems in practice.

Here is pseudo-code:

algorithm cutBeam(minimum usage, beam length)
  if only one type of piece remains
    compute how many times this piece fits in beam
    if the beam usage becomes more then the minimum usage with this amount of cuts
      record how many pieces were cut of this type
    end if
    return the beam usage
  else
    as long as you can cut more of the first available piece type from the beam
      cut one piece of the first type from the beam
      call cutBeam to get the best beam usage from the other pieces on the rest of the beam
      if the total usage is greater then the minimum usage
        minimum usage = current total usage
        record how many pieces were cut of this type
      end if
    end as long
    return minimum usage
  end if
end algorithm

Regards

P.S. You may try to adapt the solution on Wikipedia using binary search and some sort of set of points. I mean, you could make it work probably, but you will have to adjust it with additional tricks and the running time will probably grow by a logarithmic factor or smth like that.

[savavampir]

Thanks greatly for your detailed answer. I have made simple solution to this, short-pseudo:

vector<Beams> vBeams;
uint numIter = 1000;//this varies according from num. elements inserted
const double fixedLength = 10.0;
double waste = 0.0;

for numIter
    std::random_shuffle(lenghts)
    FindFirstThatFit (fill vBeams with appropriate lengths)
    waste += fixedLength - vBeams[inx].lenSum;
    keep only with smallest waste
    copy that to final vector<Beams>
...

[simeonz]

What I understand from the above code is that you use randomized algorithm. It may not give you the optimal result, but that's ok, as long as it fits your needs. I really hope it works.