Creating an Optimizer - What is the correct Math Model or formula to use ?

[roddy1212]

Hi,

I am an application developer and need to create a computer application which output should be the best possible combination of orders that would fit in a a metal stick.

I have tried by sorting the order qty in descending order, but found
that this approach was very simplistic. I need to know if there is
any Math model or formula to make this calculation.

Example of what I need to accomplish:

I have a metal sticks of 2100 MM (Stick are always the same length)

The orders could be of different lengths:

1210 MM
860 "
320 "
650 "
540 "

The goal is to cut the orders using the 2100 MM stick by scrapping the list qty of material. In this case the ideal recomendation would be:

STICK LENGTH: 2,100 MM
===========================================
To cut the stick like this: One order: 1,210 MM &
One order: 860 MM
Total qty used: 2,070 MM
Scrap Qty: 30 MM


Someone recomended me to use the Monte Carlo simulation, but I found
that this will not work for this scenario. Someone else told me this would be a combinatory analysis, but I am not sure either of this one.



I hope you can point me to the right direction.

Thanks,



Roddy.

 

[Chris Hillman]

Commutative algebra scores again?

Hi, Roddy,

It seems to me that you didn't entirely "translate" your real world problem into mathematics, but if I understand correctly you have a positive number $L$---for simplicity say a positive integer--- and a fixed list of smaller positive "lengths" $L_1 < L_2 < \dots L_r$---for simplicity say they too are integers and for later convenience set $L_1 = 1$). Now, if I guess correctly, you wish to find combinations such that $L = \sum n_j \, L_j$ (think of "padding" with ones if the integer combination of lengths you are really interested in doesn't add up to $L$; then $n_1$ is the total length of "scrap", which you want to minimize).

If so, enumerating the possible $n_1, \, n_2 \, \dots n_r$ for a given L is essentially the change counting problem, and minimizing $n_1$ is a problem solved by Hilbert using what we now recognize as Groebner basis methods in commutative algebra. Fortunately, you don't need to know much about Groebner bases to use the solution. See for example the chapter by Sturmfels in the on-line book http://www.math.uiuc.edu/Macaulay2/Book/ If I understand your problem, it's equivalent to a change counting problem where for given list of "denominations" $L_j$ you wish to minimize the number of pennies, $n_1$, which is essentially the sample problem discussed by Sturmfels. Note that Macaulay2 can be downloaded installed free of charge. I find it to be very useful for large change counting problems (and for many other things). Note that the algorithm Sturmfels discusses efficiently finds the true minimum, unlike Monte Carlo methods which yield an approximate solution, and also lists the $n_j$ which achieve this minimum value of scrap. (Sometimes more than one optimal solution is possible, and then it lists all the alternatives.)

I suggest moving this thread to...hmm... Number Theory, I suppose.

Hmm... if you wind up basing your optimizer on Macaulay2, it would be courteous to suggest that your employer send the developers a modest donation!