 #1
FranzS
 54
 12
 TL;DR Summary
 Optimization problem, multiple outputs desired (best data subdivisions): is there a way to address it?
Hello,
I'm facing a practical optimization problem for which I don't know whether a standard approach exists or not.
I would have liked to rephrase the problem in a more general way, for the sake of "good math", but I'm afraid I would leave out some details that might be relevant. So, I'm going to explain the specific reallife application and then I'll pose the related problem. Hopefully this won't be too tedious!1. Application
I need to machine (on a CNC lathe) a number ##N## of different part types (beware, ##N## is not the batch size, it's the number of the different part drawings), which are rings with a rectangular crosssection (i.e. solids of revolution [for a full 360°] where the rectangular crosssection is not adjacent to the axis of revolution), each identified by the triplet ##(d_i, D_i, h_i)##, where I'm calling ##d_i## the internal diameter, ##D_i## the external diameter, ##h_i## the height/thickness of the crosssection (the longitudinal one, as the radial thickness is already defined by ##d_i## and ##D_i##) and finally ##i=1, 2, ..., N## is just the index that identifies the specific part drawing.
Actually, ##d_i, D_i, h_i## aren't really the final dimensions: their values already include the machining allowance (i.e. they are the dimensions of the raw material, as if each of the part types had its own individual one – which is not what I want, see "2. Scope and Examples").
Also, I'm not considering additional parameters such as yearly sales forecast for each size (for simplicity and also because it's actually pretty close for all sizes).2. Scope and Examples
I have to select the proper dimensions (internal diameter and external diameter) for the raw material (steel tubes) in order to minimize scrap material during CNC machining.
The point is that – as anticipated – I don't want to select a different raw material size for each individual ##i##th part type, but I want to group several part types "under certain raw material sizes". This will of course increase scrap material, but pricewise it's still more convenient than buying ##N## individual raw material sizes (as they're going to be custommade by the supplier: the fewer the chosen sizes and the higher the quantity [kilograms or meters] for each size, the lower the price).
I will call ##M## the number of chosen raw material sizes (theoretically, I'll have ##1 \leq M \leq N##). In other words, ##M## is the number of disjoint subsets I want to define.
So, I'll start by listing the ##N## triplets ##(d_i, D_i, h_i)## in a precise order (for example, in a column) so that ##d_i \leq d_{i+1}## and ##D_i \leq D_{i+1}## ##\forall i##. It just so happens that the case ##d_i=d_{i+1} \wedge D_i=D_{i+1}## never occurs. Thus, no ordering needs to be specified for ##h_i##. The list will then be:
$$(d_1, D_1, h_1)$$
$$(d_2, D_2, h_2)$$
$$...$$
$$(d_i, D_i, h_i)$$
$$...$$
$$(d_N, D_N, h_N)$$
As said, this list will be divided in a number ##M## of disjoint subsets and each subset will contain adjacent triplets only.
I'll write a couple of simple examples for better clarity.
Example 1 (trivial, unwanted solution)
Let's say ##N=20## and ##M=1##. This is like saying a single raw material size will be chosen for machining all part types.
Thus, the raw material (steel tube) will have to have the smallest internal diameter (which is ##d_1##) and the largest external diameter (which is ##D_{20}##). Please remember that material allowance for proper CNC machining is already accounted for.
Example 2 (trivial, unwanted solution)
On the opposite side of the spectrum, let's still consider ##N=20## but now with ##M=20## as well. This is like saying I want to select a different raw material size for each individual ##i##th part type (that's exactly what I wrote I do not want to do in the reallife application).
In this case, I will have ##N## different raw material sizes, one for each of the ##N## different part types and with the very same dimensions as well.
Example 3 (possible acceptable solution)
Let's get closer to what I'd like to achieve by considering ##N=20## and ##M=4##. This is like saying four raw material sizes will be properly chosen, each for machining the corresponding subset of part types.
For example, the best solution for scrap material minimization could be:
– Raw material size #1 (smallest): internal diameter ##d_1##, external diameter ##D_4##
– Raw material size #2: internal diameter ##d_5##, external diameter ##D_{11}##
– Raw material size #3: internal diameter ##d_{12}##, external diameter ##D_{16}##
– Raw material size #4 (largest): internal diameter ##d_{17}##, external diameter ##D_{20}##
Please note!
It is always the case that the internal diameter of the smallest raw material size is ##d_1##.
It is always the case that the external diameter of the largest raw material size is ##D_N##.
It is always the case that, if a certain raw material size has an external diameter ##D_i##, the next larger raw material size will have an internal diameter ##d_{i+1}## (i.e. the subsets are disjoint and "adjacent to each other").
All this holds true for any value of ##M##.3. Problem
Given ##1<M<N## (given/decided in advance a value for ##M## that is strictly greater than ##1## and strictly less than ##N##), how can I find the exact boundaries of the ##M## subsets that minimize scrap material?
For example, going back to the specific Example 3 above (with ##N=20## and ##M=4##), is there a way to find the optimal values ##j##, ##k## and ##l## (there are ##M1## of them) that will allow me to select the following raw material optimized sizes?
– Raw material size #1 (smallest): internal diameter ##d_1##, external diameter ##D_j##
– Raw material size #2: internal diameter ##d_{j+1}##, external diameter ##D_k##
– Raw material size #3: internal diameter ##d_{k+1}##, external diameter ##D_l##
– Raw material size #4 (largest): internal diameter ##d_{l+1}##, external diameter ##D_{20}##
By the way, according to the geometry of the problem, and considering a specific example with ##M=4##, the function ##S## to be minimized (total volume of scrap material for all part types) should be, if I'm not mistaken:
$$
S(j,k,l) =
\left(
\sum_{i=1}^j
\frac{\pi}{4}
h_i
\left(
d_i^2  d_1^2 + D_j^2  D_i^2
\right)
\right)
+
\left(
\sum_{i=j+1}^k
\frac{\pi}{4}
h_i
\left(
d_i^2  d_{j+1}^2 + D_k^2  D_i^2
\right)
\right)
$$
$$
+
\left(
\sum_{i=k+1}^l
\frac{\pi}{4}
h_i
\left(
d_i^2  d_{k+1}^2 + D_l^2  D_i^2
\right)
\right)
+
\left(
\sum_{i=l+1}^N
\frac{\pi}{4}
h_i
\left(
d_i^2  d_{l+1}^2 + D_N^2  D_i^2
\right)
\right)
$$
How would you go on from here?
Of course I'm not interested in a trial & error / brute force method.
I sincerely don't know if an analytic method exists and how it could possibly give ##M1## results "at once" (via a system of equations? How to get there???).
What I'm sure about is I don't know how to approach this problem. I've not in my life studied/explored any advanced math environments/theories that might apply to this case.
Digression: this also reminds me of similar (?) optimization problems that I've faced in the past (and not solved!). For example, I was trying to find the best "twopiece" polynomial approximation of a certain function ##f(x)## on an interval ##x \in [a,b]## (linear approximation for ##a<x<c## and then quadratic approximation for ##c<x<b##), searching for the optimized value of ##c##.4. My Attempt at Solving a Simplified Case with ##M=2##
(and Why I Think I Can't Solve the Cases with ##M>2##)
NOTE: this is only for the brave (you already have my full appreciation if you stayed with me till here!)
Well, for this simplified example, I will assume that all the ##N## part types have the same height/thickness ##h##.
Thus, ##h## becomes irrelevant and the total amount of scrap material for all part types does not need to be intended as "scrap volume" anymore, but rather as "scrap area" only (I hope the concept is clear).
By the way, this is actually a good approximation in the reallife application, as all ##h_i## are very similar to each other.
With this assumption, and considering ##M=2## (i.e. I want two raw material sizes to be used for the production of all the ##N## part types), I now have to minimize the following function ##S## (total "scrap area"):
$$
S(j) =
\left(
\sum_{i=1}^j
\frac{\pi}{4}
\left(
d_i^2  d_1^2 + D_j^2  D_i^2
\right)
\right)
+
\left(
\sum_{i=j+1}^N
\frac{\pi}{4}
\left(
d_i^2  d_{j+1}^2 + D_N^2  D_i^2
\right)
\right)
$$
Then, I can simplify the expression above by ditching the common factor ## \pi / 4 ## that appears everywhere (I will call this new function ## \sigma ## instead of ##S##, as it's not the same anymore despite being still equivalent to it for my optimization purposes) and by rearranging the sums in order to isolate the constant terms:
$$
\sigma (j) =
\left(
\sum_{i=1}^j
D_j^2
\right)

\left(
\sum_{i=1}^j
d_1^2
\right)
+
\left(
\sum_{i=j+1}^N
D_N^2
\right)

\left(
\sum_{i=j+1}^N
d_{j+1}^2
\right)

\left(
\sum_{i=1}^N
D_i^2  d_i^2
\right)
$$
The last sum can be calculated promptly, as it depends only on the dimensions of all the ##N## part types, which are known values since the beginning. For a shorter notation, I will call this sum ## \Delta_0 ##.
The second and third sums only involve the constants ##d_1## and ##D_N## respectively, hence we can rewrite them in a more compact form.
The same applies to the remaining two sums, which involve ##D_j## and ##d_{j+1}##, which are independent from the index of summation ##i##.
So, the expression becomes:
$$
\sigma (j) = j D_j^2  (Nj) d_{j+1}^2  j d_1^2 + (Nj) D_N^2  \Delta_0
$$
Now, for the crucial part of the solution.
I wrote the function ##\sigma## as ##\sigma(j)##, but it seems like it depends also on ##D_j## and ##d_{j+1}##.
However, despite ##j## being just an index, I should manage to find a relation between ##j## and ##D_j##, and another relation between ##j## and ##d_{j+1}##.
In the reallife case, it turns out (luckily) that both those relations can be well approximated by linear functions. Let's call ##u(j)=u_0+u_1 j## the linear function of ##j## that well approximates ##D_j##, and ##v(j)=v_0+v_1 j## the linear function of ##j## that well approximates ##d_{j}## (we'll then input ##j+1## to obtain ##v(j+1) \approx d_{j+1}##). All coefficients ##u_0, u_1, v_0, v_1## are to be found with linear regression from the initial data (dimensions of all part types).
With these approximations, ##\sigma## becomes an explicit function of ##j## alone. Differentiate ##\sigma(j)## with respect to ##j##, cross your fingers and hope for the best.
Well, actually, I'm not really sure about this. For the linear approximations, I've got a vague feeling that we are applying the two linear regressions in the "##i## world" instead of the "##j## world". Sloppy way of expressing myself, I know, but I hope you get the idea.
My doubts also arise from the fact that – if I apply the same reasoning in the case with ##M>2## (so that I will have more than one "boundary index", i.e. ##j##, ##k##, etc.) – the ##j##, ##k##, etc. indexes themselves will be indistinguishable using my method.
Please enlighten me!THE END
My sincere apologies for the lengthy post, and my biggest "thank you" to all of you who took the time to read it.
I'm facing a practical optimization problem for which I don't know whether a standard approach exists or not.
I would have liked to rephrase the problem in a more general way, for the sake of "good math", but I'm afraid I would leave out some details that might be relevant. So, I'm going to explain the specific reallife application and then I'll pose the related problem. Hopefully this won't be too tedious!1. Application
I need to machine (on a CNC lathe) a number ##N## of different part types (beware, ##N## is not the batch size, it's the number of the different part drawings), which are rings with a rectangular crosssection (i.e. solids of revolution [for a full 360°] where the rectangular crosssection is not adjacent to the axis of revolution), each identified by the triplet ##(d_i, D_i, h_i)##, where I'm calling ##d_i## the internal diameter, ##D_i## the external diameter, ##h_i## the height/thickness of the crosssection (the longitudinal one, as the radial thickness is already defined by ##d_i## and ##D_i##) and finally ##i=1, 2, ..., N## is just the index that identifies the specific part drawing.
Actually, ##d_i, D_i, h_i## aren't really the final dimensions: their values already include the machining allowance (i.e. they are the dimensions of the raw material, as if each of the part types had its own individual one – which is not what I want, see "2. Scope and Examples").
Also, I'm not considering additional parameters such as yearly sales forecast for each size (for simplicity and also because it's actually pretty close for all sizes).2. Scope and Examples
I have to select the proper dimensions (internal diameter and external diameter) for the raw material (steel tubes) in order to minimize scrap material during CNC machining.
The point is that – as anticipated – I don't want to select a different raw material size for each individual ##i##th part type, but I want to group several part types "under certain raw material sizes". This will of course increase scrap material, but pricewise it's still more convenient than buying ##N## individual raw material sizes (as they're going to be custommade by the supplier: the fewer the chosen sizes and the higher the quantity [kilograms or meters] for each size, the lower the price).
I will call ##M## the number of chosen raw material sizes (theoretically, I'll have ##1 \leq M \leq N##). In other words, ##M## is the number of disjoint subsets I want to define.
So, I'll start by listing the ##N## triplets ##(d_i, D_i, h_i)## in a precise order (for example, in a column) so that ##d_i \leq d_{i+1}## and ##D_i \leq D_{i+1}## ##\forall i##. It just so happens that the case ##d_i=d_{i+1} \wedge D_i=D_{i+1}## never occurs. Thus, no ordering needs to be specified for ##h_i##. The list will then be:
$$(d_1, D_1, h_1)$$
$$(d_2, D_2, h_2)$$
$$...$$
$$(d_i, D_i, h_i)$$
$$...$$
$$(d_N, D_N, h_N)$$
As said, this list will be divided in a number ##M## of disjoint subsets and each subset will contain adjacent triplets only.
I'll write a couple of simple examples for better clarity.
Example 1 (trivial, unwanted solution)
Let's say ##N=20## and ##M=1##. This is like saying a single raw material size will be chosen for machining all part types.
Thus, the raw material (steel tube) will have to have the smallest internal diameter (which is ##d_1##) and the largest external diameter (which is ##D_{20}##). Please remember that material allowance for proper CNC machining is already accounted for.
Example 2 (trivial, unwanted solution)
On the opposite side of the spectrum, let's still consider ##N=20## but now with ##M=20## as well. This is like saying I want to select a different raw material size for each individual ##i##th part type (that's exactly what I wrote I do not want to do in the reallife application).
In this case, I will have ##N## different raw material sizes, one for each of the ##N## different part types and with the very same dimensions as well.
Example 3 (possible acceptable solution)
Let's get closer to what I'd like to achieve by considering ##N=20## and ##M=4##. This is like saying four raw material sizes will be properly chosen, each for machining the corresponding subset of part types.
For example, the best solution for scrap material minimization could be:
– Raw material size #1 (smallest): internal diameter ##d_1##, external diameter ##D_4##
– Raw material size #2: internal diameter ##d_5##, external diameter ##D_{11}##
– Raw material size #3: internal diameter ##d_{12}##, external diameter ##D_{16}##
– Raw material size #4 (largest): internal diameter ##d_{17}##, external diameter ##D_{20}##
Please note!
It is always the case that the internal diameter of the smallest raw material size is ##d_1##.
It is always the case that the external diameter of the largest raw material size is ##D_N##.
It is always the case that, if a certain raw material size has an external diameter ##D_i##, the next larger raw material size will have an internal diameter ##d_{i+1}## (i.e. the subsets are disjoint and "adjacent to each other").
All this holds true for any value of ##M##.3. Problem
Given ##1<M<N## (given/decided in advance a value for ##M## that is strictly greater than ##1## and strictly less than ##N##), how can I find the exact boundaries of the ##M## subsets that minimize scrap material?
For example, going back to the specific Example 3 above (with ##N=20## and ##M=4##), is there a way to find the optimal values ##j##, ##k## and ##l## (there are ##M1## of them) that will allow me to select the following raw material optimized sizes?
– Raw material size #1 (smallest): internal diameter ##d_1##, external diameter ##D_j##
– Raw material size #2: internal diameter ##d_{j+1}##, external diameter ##D_k##
– Raw material size #3: internal diameter ##d_{k+1}##, external diameter ##D_l##
– Raw material size #4 (largest): internal diameter ##d_{l+1}##, external diameter ##D_{20}##
By the way, according to the geometry of the problem, and considering a specific example with ##M=4##, the function ##S## to be minimized (total volume of scrap material for all part types) should be, if I'm not mistaken:
$$
S(j,k,l) =
\left(
\sum_{i=1}^j
\frac{\pi}{4}
h_i
\left(
d_i^2  d_1^2 + D_j^2  D_i^2
\right)
\right)
+
\left(
\sum_{i=j+1}^k
\frac{\pi}{4}
h_i
\left(
d_i^2  d_{j+1}^2 + D_k^2  D_i^2
\right)
\right)
$$
$$
+
\left(
\sum_{i=k+1}^l
\frac{\pi}{4}
h_i
\left(
d_i^2  d_{k+1}^2 + D_l^2  D_i^2
\right)
\right)
+
\left(
\sum_{i=l+1}^N
\frac{\pi}{4}
h_i
\left(
d_i^2  d_{l+1}^2 + D_N^2  D_i^2
\right)
\right)
$$
How would you go on from here?
Of course I'm not interested in a trial & error / brute force method.
I sincerely don't know if an analytic method exists and how it could possibly give ##M1## results "at once" (via a system of equations? How to get there???).
What I'm sure about is I don't know how to approach this problem. I've not in my life studied/explored any advanced math environments/theories that might apply to this case.
Digression: this also reminds me of similar (?) optimization problems that I've faced in the past (and not solved!). For example, I was trying to find the best "twopiece" polynomial approximation of a certain function ##f(x)## on an interval ##x \in [a,b]## (linear approximation for ##a<x<c## and then quadratic approximation for ##c<x<b##), searching for the optimized value of ##c##.4. My Attempt at Solving a Simplified Case with ##M=2##
(and Why I Think I Can't Solve the Cases with ##M>2##)
NOTE: this is only for the brave (you already have my full appreciation if you stayed with me till here!)
Well, for this simplified example, I will assume that all the ##N## part types have the same height/thickness ##h##.
Thus, ##h## becomes irrelevant and the total amount of scrap material for all part types does not need to be intended as "scrap volume" anymore, but rather as "scrap area" only (I hope the concept is clear).
By the way, this is actually a good approximation in the reallife application, as all ##h_i## are very similar to each other.
With this assumption, and considering ##M=2## (i.e. I want two raw material sizes to be used for the production of all the ##N## part types), I now have to minimize the following function ##S## (total "scrap area"):
$$
S(j) =
\left(
\sum_{i=1}^j
\frac{\pi}{4}
\left(
d_i^2  d_1^2 + D_j^2  D_i^2
\right)
\right)
+
\left(
\sum_{i=j+1}^N
\frac{\pi}{4}
\left(
d_i^2  d_{j+1}^2 + D_N^2  D_i^2
\right)
\right)
$$
Then, I can simplify the expression above by ditching the common factor ## \pi / 4 ## that appears everywhere (I will call this new function ## \sigma ## instead of ##S##, as it's not the same anymore despite being still equivalent to it for my optimization purposes) and by rearranging the sums in order to isolate the constant terms:
$$
\sigma (j) =
\left(
\sum_{i=1}^j
D_j^2
\right)

\left(
\sum_{i=1}^j
d_1^2
\right)
+
\left(
\sum_{i=j+1}^N
D_N^2
\right)

\left(
\sum_{i=j+1}^N
d_{j+1}^2
\right)

\left(
\sum_{i=1}^N
D_i^2  d_i^2
\right)
$$
The last sum can be calculated promptly, as it depends only on the dimensions of all the ##N## part types, which are known values since the beginning. For a shorter notation, I will call this sum ## \Delta_0 ##.
The second and third sums only involve the constants ##d_1## and ##D_N## respectively, hence we can rewrite them in a more compact form.
The same applies to the remaining two sums, which involve ##D_j## and ##d_{j+1}##, which are independent from the index of summation ##i##.
So, the expression becomes:
$$
\sigma (j) = j D_j^2  (Nj) d_{j+1}^2  j d_1^2 + (Nj) D_N^2  \Delta_0
$$
Now, for the crucial part of the solution.
I wrote the function ##\sigma## as ##\sigma(j)##, but it seems like it depends also on ##D_j## and ##d_{j+1}##.
However, despite ##j## being just an index, I should manage to find a relation between ##j## and ##D_j##, and another relation between ##j## and ##d_{j+1}##.
In the reallife case, it turns out (luckily) that both those relations can be well approximated by linear functions. Let's call ##u(j)=u_0+u_1 j## the linear function of ##j## that well approximates ##D_j##, and ##v(j)=v_0+v_1 j## the linear function of ##j## that well approximates ##d_{j}## (we'll then input ##j+1## to obtain ##v(j+1) \approx d_{j+1}##). All coefficients ##u_0, u_1, v_0, v_1## are to be found with linear regression from the initial data (dimensions of all part types).
With these approximations, ##\sigma## becomes an explicit function of ##j## alone. Differentiate ##\sigma(j)## with respect to ##j##, cross your fingers and hope for the best.
Well, actually, I'm not really sure about this. For the linear approximations, I've got a vague feeling that we are applying the two linear regressions in the "##i## world" instead of the "##j## world". Sloppy way of expressing myself, I know, but I hope you get the idea.
My doubts also arise from the fact that – if I apply the same reasoning in the case with ##M>2## (so that I will have more than one "boundary index", i.e. ##j##, ##k##, etc.) – the ##j##, ##k##, etc. indexes themselves will be indistinguishable using my method.
Please enlighten me!THE END
My sincere apologies for the lengthy post, and my biggest "thank you" to all of you who took the time to read it.
Last edited: