Optimization problem
Locked
 
|
I'd like advice on possible ways to solve the following problem
(plumbers must surely face this all the time). I need to cut a set of metal tubes of varying lengths from standard length (6 meter) galvanized conduit stock. The goal is to find the number of tubes I need to buy, and the order of cuts to produce the minimum amount of leftover, unused tube. I'm interested in what types of solutions people use for similar 1-dimensional problems, e.g. linear programming, greedy algorithms, etc. (I've been Googling). I'm only looking to cut around 15-25 pieces, so my gut feeling is that an exhaustive search of all possible solutions, though probably NP-hard, would be feasible to perform. Working programs, as well as libraries in any language would be a bonus. ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com archives back to 2003: http://friam.471366.n2.nabble.com/ FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove |
|
|
Two possible approaches are: a) Solve the problem yourself. Use one or a combination of standard algorithms ( eg you mentioned linear programming and greedy algorithms, there are many more of course) and/or your own custom algorithm. If you wish to go this route and want to learn about the subject, I recommend the series of MOOCS by Stanford's Tim Roughgarden https://www.coursera.org/specializations/algorithms Or, I think yours is probably a knapsack -type problem and the MOOC https://www.coursera.org/learn/discrete-optimization covers that relatively well. b) But if you just want to get the solution you can use optimization software like https://www.ibm.com/za-en/products/ilog-cplex-optimization-studio (they have a free edition that will be good enough for your application) will solve it for you without you necessarily knowing how the software does it. On Fri, 20 Sep 2019 at 21:00, Gary Schiltz <[hidden email]> wrote: I'd like advice on possible ways to solve the following problem ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com archives back to 2003: http://friam.471366.n2.nabble.com/ FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove |
|
|
And if you want to know how it works, I suggest SCIP. https://scip.zib.de/ From: Friam <[hidden email]> on behalf of Pieter Steenekamp <[hidden email]> Two possible approaches are: a) Solve the problem yourself. Use one or a combination of standard algorithms ( eg you mentioned linear programming and greedy algorithms, there are many more of course) and/or your own custom algorithm. If you wish to go this route and
want to learn about the subject, I recommend the series of MOOCS by Stanford's Tim Roughgarden https://www.coursera.org/specializations/algorithms Or, I think yours is probably a knapsack -type problem and the MOOC https://www.coursera.org/learn/discrete-optimization covers that relatively well. b) But if you just want to get the solution you can use optimization software like https://www.ibm.com/za-en/products/ilog-cplex-optimization-studio (they have
a free edition that will be good enough for your application) will solve it for you without you necessarily knowing how the software does it. On Fri, 20 Sep 2019 at 21:00, Gary Schiltz <[hidden email]> wrote:
============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com archives back to 2003: http://friam.471366.n2.nabble.com/ FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove |
|
|
In reply to this post by Pieter Steenekamp
Thanks for the links, Peter. I will probably use that software or
similar, to get a quick solution, then look at the MOOCs. On Fri, Sep 20, 2019 at 2:52 PM Pieter Steenekamp <[hidden email]> wrote: > > Two possible approaches are: > a) Solve the problem yourself. Use one or a combination of standard algorithms ( eg you mentioned linear programming and greedy algorithms, there are many more of course) and/or your own custom algorithm. If you wish to go this route and want to learn about the subject, I recommend the series of MOOCS by Stanford's Tim Roughgarden https://www.coursera.org/specializations/algorithms > Or, I think yours is probably a knapsack -type problem and the MOOC https://www.coursera.org/learn/discrete-optimization covers that relatively well. > b) But if you just want to get the solution you can use optimization software like https://www.ibm.com/za-en/products/ilog-cplex-optimization-studio (they have a free edition that will be good enough for your application) will solve it for you without you necessarily knowing how the software does it. > > On Fri, 20 Sep 2019 at 21:00, Gary Schiltz <[hidden email]> wrote: >> >> I'd like advice on possible ways to solve the following problem >> (plumbers must surely face this all the time). I need to cut a set of >> metal tubes of varying lengths from standard length (6 meter) >> galvanized conduit stock. The goal is to find the number of tubes I >> need to buy, and the order of cuts to produce the minimum amount of >> leftover, unused tube. I'm interested in what types of solutions >> people use for similar 1-dimensional problems, e.g. linear >> programming, greedy algorithms, etc. (I've been Googling). I'm only >> looking to cut around 15-25 pieces, so my gut feeling is that an >> exhaustive search of all possible solutions, though probably NP-hard, >> would be feasible to perform. Working programs, as well as libraries >> in any language would be a bonus. >> >> ============================================================ >> FRIAM Applied Complexity Group listserv >> Meets Fridays 9a-11:30 at cafe at St. John's College >> to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com >> archives back to 2003: http://friam.471366.n2.nabble.com/ >> FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove > > ============================================================ > FRIAM Applied Complexity Group listserv > Meets Fridays 9a-11:30 at cafe at St. John's College > to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com > archives back to 2003: http://friam.471366.n2.nabble.com/ > FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com archives back to 2003: http://friam.471366.n2.nabble.com/ FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove |
|
|
Gary -
I *patently don't* recommend my method, though it does have some charms. I recently was faced with a similar problem to yours where I needed to cut and install trim around the perimeter of the room (with door openings) I just layed hardwood floor in. Rather than go into it in detail (I already did that and realized it was a TL;DR as usual, so cut it) I will just say that I approach these problems as *satisficing* and *constraint* problems rather than *optimization*. Once I had a candidate layout, I simply looked at the results and determined that the *waste* was acceptable. Depending on the circumstances I sometimes prefer to have for example, 2 3' leftovers rather than 1 5' leftover, other times, vice-versa, depending on how I might use said leftovers in some future application (or hedging against a mistake in my measuring/cutting). Care to share what your actual conduit/pipe project is? - Steve > Thanks for the links, Peter. I will probably use that software or > similar, to get a quick solution, then look at the MOOCs. > > On Fri, Sep 20, 2019 at 2:52 PM Pieter Steenekamp > <[hidden email]> wrote: >> Two possible approaches are: >> a) Solve the problem yourself. Use one or a combination of standard algorithms ( eg you mentioned linear programming and greedy algorithms, there are many more of course) and/or your own custom algorithm. If you wish to go this route and want to learn about the subject, I recommend the series of MOOCS by Stanford's Tim Roughgarden https://www.coursera.org/specializations/algorithms >> Or, I think yours is probably a knapsack -type problem and the MOOC https://www.coursera.org/learn/discrete-optimization covers that relatively well. >> b) But if you just want to get the solution you can use optimization software like https://www.ibm.com/za-en/products/ilog-cplex-optimization-studio (they have a free edition that will be good enough for your application) will solve it for you without you necessarily knowing how the software does it. >> >> On Fri, 20 Sep 2019 at 21:00, Gary Schiltz <[hidden email]> wrote: >>> I'd like advice on possible ways to solve the following problem >>> (plumbers must surely face this all the time). I need to cut a set of >>> metal tubes of varying lengths from standard length (6 meter) >>> galvanized conduit stock. The goal is to find the number of tubes I >>> need to buy, and the order of cuts to produce the minimum amount of >>> leftover, unused tube. I'm interested in what types of solutions >>> people use for similar 1-dimensional problems, e.g. linear >>> programming, greedy algorithms, etc. (I've been Googling). I'm only >>> looking to cut around 15-25 pieces, so my gut feeling is that an >>> exhaustive search of all possible solutions, though probably NP-hard, >>> would be feasible to perform. Working programs, as well as libraries >>> in any language would be a bonus. >>> >>> ============================================================ >>> FRIAM Applied Complexity Group listserv >>> Meets Fridays 9a-11:30 at cafe at St. John's College >>> to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com >>> archives back to 2003: http://friam.471366.n2.nabble.com/ >>> FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove >> ============================================================ >> FRIAM Applied Complexity Group listserv >> Meets Fridays 9a-11:30 at cafe at St. John's College >> to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com >> archives back to 2003: http://friam.471366.n2.nabble.com/ >> FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove > ============================================================ > FRIAM Applied Complexity Group listserv > Meets Fridays 9a-11:30 at cafe at St. John's College > to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com > archives back to 2003: http://friam.471366.n2.nabble.com/ > FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com archives back to 2003: http://friam.471366.n2.nabble.com/ FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove |
|
|
In my experience, general purpose constraint and SMT solvers tend to have poor performance compared to linear relaxation techniques found in mathematical optimization products like CPLEX (which also have constraints but from a limited repertoire). It depends on the nature of your constraints whether CPLEX will work, but I think it will for your problem.
On 9/20/19, 3:55 PM, "Friam on behalf of Steven A Smith" <[hidden email] on behalf of [hidden email]> wrote: Gary - I *patently don't* recommend my method, though it does have some charms. I recently was faced with a similar problem to yours where I needed to cut and install trim around the perimeter of the room (with door openings) I just layed hardwood floor in. Rather than go into it in detail (I already did that and realized it was a TL;DR as usual, so cut it) I will just say that I approach these problems as *satisficing* and *constraint* problems rather than *optimization*. Once I had a candidate layout, I simply looked at the results and determined that the *waste* was acceptable. Depending on the circumstances I sometimes prefer to have for example, 2 3' leftovers rather than 1 5' leftover, other times, vice-versa, depending on how I might use said leftovers in some future application (or hedging against a mistake in my measuring/cutting). Care to share what your actual conduit/pipe project is? - Steve > Thanks for the links, Peter. I will probably use that software or > similar, to get a quick solution, then look at the MOOCs. > > On Fri, Sep 20, 2019 at 2:52 PM Pieter Steenekamp > <[hidden email]> wrote: >> Two possible approaches are: >> a) Solve the problem yourself. Use one or a combination of standard algorithms ( eg you mentioned linear programming and greedy algorithms, there are many more of course) and/or your own custom algorithm. If you wish to go this route and want to learn about the subject, I recommend the series of MOOCS by Stanford's Tim Roughgarden https://www.coursera.org/specializations/algorithms >> Or, I think yours is probably a knapsack -type problem and the MOOC https://www.coursera.org/learn/discrete-optimization covers that relatively well. >> b) But if you just want to get the solution you can use optimization software like https://www.ibm.com/za-en/products/ilog-cplex-optimization-studio (they have a free edition that will be good enough for your application) will solve it for you without you necessarily knowing how the software does it. >> >> On Fri, 20 Sep 2019 at 21:00, Gary Schiltz <[hidden email]> wrote: >>> I'd like advice on possible ways to solve the following problem >>> (plumbers must surely face this all the time). I need to cut a set of >>> metal tubes of varying lengths from standard length (6 meter) >>> galvanized conduit stock. The goal is to find the number of tubes I >>> need to buy, and the order of cuts to produce the minimum amount of >>> leftover, unused tube. I'm interested in what types of solutions >>> people use for similar 1-dimensional problems, e.g. linear >>> programming, greedy algorithms, etc. (I've been Googling). I'm only >>> looking to cut around 15-25 pieces, so my gut feeling is that an >>> exhaustive search of all possible solutions, though probably NP-hard, >>> would be feasible to perform. Working programs, as well as libraries >>> in any language would be a bonus. >>> >>> ============================================================ >>> FRIAM Applied Complexity Group listserv >>> Meets Fridays 9a-11:30 at cafe at St. John's College >>> to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com >>> archives back to 2003: http://friam.471366.n2.nabble.com/ >>> FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove >> ============================================================ >> FRIAM Applied Complexity Group listserv >> Meets Fridays 9a-11:30 at cafe at St. John's College >> to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com >> archives back to 2003: http://friam.471366.n2.nabble.com/ >> FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove > ============================================================ > FRIAM Applied Complexity Group listserv > Meets Fridays 9a-11:30 at cafe at St. John's College > to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com > archives back to 2003: http://friam.471366.n2.nabble.com/ > FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com archives back to 2003: http://friam.471366.n2.nabble.com/ FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com archives back to 2003: http://friam.471366.n2.nabble.com/ FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove |
|
|
In reply to this post by Steve Smith
Hey Steve. The actual project is nothing elaborate. My house has a
couple or three dozsen horizontally sliding windows with pretty weak locks. Since I've had a couple of break-ins in the past, I decided that the easiest way to shore up security for that aspect of the house is to just cut short pieces of 3/4 inch conduit to lay horizontally in the spaces where the windows slide. When I want to open a window, I will just stand its conduit piece up, and when I want to "lock" it again, just lay it back horizontally. I asked on FRIAM because instead of just eyeballing it and having lots of extra (even potentially useful in the future) pieces left over, I'd rather use my (and FRIAM's) brain to look at possible ways of optimizing this. Kind of fun actually putting my mind to something for a change (retirement can be boring if you're not careful). On Fri, Sep 20, 2019 at 5:55 PM Steven A Smith <[hidden email]> wrote: > > Gary - > > I *patently don't* recommend my method, though it does have some > charms. I recently was faced with a similar problem to yours where I > needed to cut and install trim around the perimeter of the room (with > door openings) I just layed hardwood floor in. > > Rather than go into it in detail (I already did that and realized it was > a TL;DR as usual, so cut it) I will just say that I approach these > problems as *satisficing* and *constraint* problems rather than > *optimization*. Once I had a candidate layout, I simply looked at the > results and determined that the *waste* was acceptable. Depending on > the circumstances I sometimes prefer to have for example, 2 3' leftovers > rather than 1 5' leftover, other times, vice-versa, depending on how I > might use said leftovers in some future application (or hedging against > a mistake in my measuring/cutting). > > Care to share what your actual conduit/pipe project is? > > - Steve > > > > Thanks for the links, Peter. I will probably use that software or > > similar, to get a quick solution, then look at the MOOCs. > > > > On Fri, Sep 20, 2019 at 2:52 PM Pieter Steenekamp > > <[hidden email]> wrote: > >> Two possible approaches are: > >> a) Solve the problem yourself. Use one or a combination of standard algorithms ( eg you mentioned linear programming and greedy algorithms, there are many more of course) and/or your own custom algorithm. If you wish to go this route and want to learn about the subject, I recommend the series of MOOCS by Stanford's Tim Roughgarden https://www.coursera.org/specializations/algorithms > >> Or, I think yours is probably a knapsack -type problem and the MOOC https://www.coursera.org/learn/discrete-optimization covers that relatively well. > >> b) But if you just want to get the solution you can use optimization software like https://www.ibm.com/za-en/products/ilog-cplex-optimization-studio (they have a free edition that will be good enough for your application) will solve it for you without you necessarily knowing how the software does it. > >> > >> On Fri, 20 Sep 2019 at 21:00, Gary Schiltz <[hidden email]> wrote: > >>> I'd like advice on possible ways to solve the following problem > >>> (plumbers must surely face this all the time). I need to cut a set of > >>> metal tubes of varying lengths from standard length (6 meter) > >>> galvanized conduit stock. The goal is to find the number of tubes I > >>> need to buy, and the order of cuts to produce the minimum amount of > >>> leftover, unused tube. I'm interested in what types of solutions > >>> people use for similar 1-dimensional problems, e.g. linear > >>> programming, greedy algorithms, etc. (I've been Googling). I'm only > >>> looking to cut around 15-25 pieces, so my gut feeling is that an > >>> exhaustive search of all possible solutions, though probably NP-hard, > >>> would be feasible to perform. Working programs, as well as libraries > >>> in any language would be a bonus. > >>> > >>> ============================================================ > >>> FRIAM Applied Complexity Group listserv > >>> Meets Fridays 9a-11:30 at cafe at St. John's College > >>> to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com > >>> archives back to 2003: http://friam.471366.n2.nabble.com/ > >>> FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove > >> ============================================================ > >> FRIAM Applied Complexity Group listserv > >> Meets Fridays 9a-11:30 at cafe at St. John's College > >> to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com > >> archives back to 2003: http://friam.471366.n2.nabble.com/ > >> FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove > > ============================================================ > > FRIAM Applied Complexity Group listserv > > Meets Fridays 9a-11:30 at cafe at St. John's College > > to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com > > archives back to 2003: http://friam.471366.n2.nabble.com/ > > FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove > > > ============================================================ > FRIAM Applied Complexity Group listserv > Meets Fridays 9a-11:30 at cafe at St. John's College > to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com > archives back to 2003: http://friam.471366.n2.nabble.com/ > FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com archives back to 2003: http://friam.471366.n2.nabble.com/ FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove |
|
|
In reply to this post by Gary Schiltz-4
Algorithm with guaranteed optimal:
* assumes welder $ < optimization design and compute time _______________________________________________________________________ [hidden email] CEO, Simtable http://www.simtable.com 1600 Lena St #D1, Santa Fe, NM 87505 office: (505)995-0206 mobile: (505)577-5828 twitter: @simtable On Fri, Sep 20, 2019 at 1:56 PM Gary Schiltz <[hidden email]> wrote: Thanks for the links, Peter. I will probably use that software or ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com archives back to 2003: http://friam.471366.n2.nabble.com/ FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove |
|
|
In reply to this post by Marcus G. Daniels
Marcus, for the couple of dozen pieces I need to cut, I suspect a
purely brute force solution would be adequate. I've only begun to think about what an extremely naive algorithm would look like. On Fri, Sep 20, 2019 at 6:07 PM Marcus Daniels <[hidden email]> wrote: > > In my experience, general purpose constraint and SMT solvers tend to have poor performance compared to linear relaxation techniques found in mathematical optimization products like CPLEX (which also have constraints but from a limited repertoire). It depends on the nature of your constraints whether CPLEX will work, but I think it will for your problem. > > On 9/20/19, 3:55 PM, "Friam on behalf of Steven A Smith" <[hidden email] on behalf of [hidden email]> wrote: > > Gary - > > I *patently don't* recommend my method, though it does have some > charms. I recently was faced with a similar problem to yours where I > needed to cut and install trim around the perimeter of the room (with > door openings) I just layed hardwood floor in. > > Rather than go into it in detail (I already did that and realized it was > a TL;DR as usual, so cut it) I will just say that I approach these > problems as *satisficing* and *constraint* problems rather than > *optimization*. Once I had a candidate layout, I simply looked at the > results and determined that the *waste* was acceptable. Depending on > the circumstances I sometimes prefer to have for example, 2 3' leftovers > rather than 1 5' leftover, other times, vice-versa, depending on how I > might use said leftovers in some future application (or hedging against > a mistake in my measuring/cutting). > > Care to share what your actual conduit/pipe project is? > > - Steve > > > > Thanks for the links, Peter. I will probably use that software or > > similar, to get a quick solution, then look at the MOOCs. > > > > On Fri, Sep 20, 2019 at 2:52 PM Pieter Steenekamp > > <[hidden email]> wrote: > >> Two possible approaches are: > >> a) Solve the problem yourself. Use one or a combination of standard algorithms ( eg you mentioned linear programming and greedy algorithms, there are many more of course) and/or your own custom algorithm. If you wish to go this route and want to learn about the subject, I recommend the series of MOOCS by Stanford's Tim Roughgarden https://www.coursera.org/specializations/algorithms > >> Or, I think yours is probably a knapsack -type problem and the MOOC https://www.coursera.org/learn/discrete-optimization covers that relatively well. > >> b) But if you just want to get the solution you can use optimization software like https://www.ibm.com/za-en/products/ilog-cplex-optimization-studio (they have a free edition that will be good enough for your application) will solve it for you without you necessarily knowing how the software does it. > >> > >> On Fri, 20 Sep 2019 at 21:00, Gary Schiltz <[hidden email]> wrote: > >>> I'd like advice on possible ways to solve the following problem > >>> (plumbers must surely face this all the time). I need to cut a set of > >>> metal tubes of varying lengths from standard length (6 meter) > >>> galvanized conduit stock. The goal is to find the number of tubes I > >>> need to buy, and the order of cuts to produce the minimum amount of > >>> leftover, unused tube. I'm interested in what types of solutions > >>> people use for similar 1-dimensional problems, e.g. linear > >>> programming, greedy algorithms, etc. (I've been Googling). I'm only > >>> looking to cut around 15-25 pieces, so my gut feeling is that an > >>> exhaustive search of all possible solutions, though probably NP-hard, > >>> would be feasible to perform. Working programs, as well as libraries > >>> in any language would be a bonus. > >>> > >>> ============================================================ > >>> FRIAM Applied Complexity Group listserv > >>> Meets Fridays 9a-11:30 at cafe at St. John's College > >>> to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com > >>> archives back to 2003: http://friam.471366.n2.nabble.com/ > >>> FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove > >> ============================================================ > >> FRIAM Applied Complexity Group listserv > >> Meets Fridays 9a-11:30 at cafe at St. John's College > >> to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com > >> archives back to 2003: http://friam.471366.n2.nabble.com/ > >> FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove > > ============================================================ > > FRIAM Applied Complexity Group listserv > > Meets Fridays 9a-11:30 at cafe at St. John's College > > to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com > > archives back to 2003: http://friam.471366.n2.nabble.com/ > > FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove > > > ============================================================ > FRIAM Applied Complexity Group listserv > Meets Fridays 9a-11:30 at cafe at St. John's College > to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com > archives back to 2003: http://friam.471366.n2.nabble.com/ > FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove > > > ============================================================ > FRIAM Applied Complexity Group listserv > Meets Fridays 9a-11:30 at cafe at St. John's College > to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com > archives back to 2003: http://friam.471366.n2.nabble.com/ > FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com archives back to 2003: http://friam.471366.n2.nabble.com/ FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove |
|
|
In reply to this post by Stephen Guerin-5
Steve, that makes my day! Your solution is like Kirk's way of passing
the "Kobayashi Maru" training exercise. https://en.wikipedia.org/wiki/Kobayashi_Maru On Fri, Sep 20, 2019 at 6:23 PM Stephen Guerin <[hidden email]> wrote: > > Algorithm with guaranteed optimal: > > purchase ceil(TotalLengthNeeded / 6) tubes > Weld purchased tubes into one long tube * > Cut what you need in any order > > * assumes welder $ < optimization design and compute time > _______________________________________________________________________ > [hidden email] > CEO, Simtable http://www.simtable.com > 1600 Lena St #D1, Santa Fe, NM 87505 > office: (505)995-0206 mobile: (505)577-5828 > twitter: @simtable > > > On Fri, Sep 20, 2019 at 1:56 PM Gary Schiltz <[hidden email]> wrote: >> >> Thanks for the links, Peter. I will probably use that software or >> similar, to get a quick solution, then look at the MOOCs. >> >> On Fri, Sep 20, 2019 at 2:52 PM Pieter Steenekamp >> <[hidden email]> wrote: >> > >> > Two possible approaches are: >> > a) Solve the problem yourself. Use one or a combination of standard algorithms ( eg you mentioned linear programming and greedy algorithms, there are many more of course) and/or your own custom algorithm. If you wish to go this route and want to learn about the subject, I recommend the series of MOOCS by Stanford's Tim Roughgarden https://www.coursera.org/specializations/algorithms >> > Or, I think yours is probably a knapsack -type problem and the MOOC https://www.coursera.org/learn/discrete-optimization covers that relatively well. >> > b) But if you just want to get the solution you can use optimization software like https://www.ibm.com/za-en/products/ilog-cplex-optimization-studio (they have a free edition that will be good enough for your application) will solve it for you without you necessarily knowing how the software does it. >> > >> > On Fri, 20 Sep 2019 at 21:00, Gary Schiltz <[hidden email]> wrote: >> >> >> >> I'd like advice on possible ways to solve the following problem >> >> (plumbers must surely face this all the time). I need to cut a set of >> >> metal tubes of varying lengths from standard length (6 meter) >> >> galvanized conduit stock. The goal is to find the number of tubes I >> >> need to buy, and the order of cuts to produce the minimum amount of >> >> leftover, unused tube. I'm interested in what types of solutions >> >> people use for similar 1-dimensional problems, e.g. linear >> >> programming, greedy algorithms, etc. (I've been Googling). I'm only >> >> looking to cut around 15-25 pieces, so my gut feeling is that an >> >> exhaustive search of all possible solutions, though probably NP-hard, >> >> would be feasible to perform. Working programs, as well as libraries >> >> in any language would be a bonus. >> >> >> >> ============================================================ >> >> FRIAM Applied Complexity Group listserv >> >> Meets Fridays 9a-11:30 at cafe at St. John's College >> >> to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com >> >> archives back to 2003: http://friam.471366.n2.nabble.com/ >> >> FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove >> > >> > ============================================================ >> > FRIAM Applied Complexity Group listserv >> > Meets Fridays 9a-11:30 at cafe at St. John's College >> > to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com >> > archives back to 2003: http://friam.471366.n2.nabble.com/ >> > FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove >> >> ============================================================ >> FRIAM Applied Complexity Group listserv >> Meets Fridays 9a-11:30 at cafe at St. John's College >> to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com >> archives back to 2003: http://friam.471366.n2.nabble.com/ >> FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove > > ============================================================ > FRIAM Applied Complexity Group listserv > Meets Fridays 9a-11:30 at cafe at St. John's College > to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com > archives back to 2003: http://friam.471366.n2.nabble.com/ > FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com archives back to 2003: http://friam.471366.n2.nabble.com/ FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove |
|
|
In reply to this post by Gary Schiltz-4
Gary -
I understand better now... I definitely agree that the *most* naive eyeballing methods can be excruciatingly wasteful. I presume that your conduit length requirements are not precise... that you might be designing them to allow for leaving the window partially open but otherwise not subject to intrusion or compromise? That seems to complicate the problem but may pose opportunities. In particular, *I* might be looking for solutions which leave me with a *minimum* of leftover conduit by making them longer than their shortest possibles in some cases. Or looking at it the other way, even if you don't need to leave the windows open much when "locked" a more complete use of the material might be obtained by relaxing the length a little without compromising security (if a given window can only be opened a few inches for example). I will be interested in hearing the results of whatever optimization (or satisficing) method you use yields. - Steve PS. regarding guerin's solution, an alternate would be to measure as suggested, then cut naively until the remaining spaces are larger than the remaining pieces. Only *then* does one break out the welder and begin to piece together as-needed. I don't think these are equivalent. It also occurs to me that *2* pieces of conduit (end to end, unwelded) in a window channel might be *nearly* as effective as a single piece, albeit less elegant? > Hey Steve. The actual project is nothing elaborate. My house has a > couple or three dozsen horizontally sliding windows with pretty weak > locks. Since I've had a couple of break-ins in the past, I decided > that the easiest way to shore up security for that aspect of the house > is to just cut short pieces of 3/4 inch conduit to lay horizontally in > the spaces where the windows slide. When I want to open a window, I > will just stand its conduit piece up, and when I want to "lock" it > again, just lay it back horizontally. I asked on FRIAM because instead > of just eyeballing it and having lots of extra (even potentially > useful in the future) pieces left over, I'd rather use my (and > FRIAM's) brain to look at possible ways of optimizing this. Kind of > fun actually putting my mind to something for a change (retirement can > be boring if you're not careful). > > On Fri, Sep 20, 2019 at 5:55 PM Steven A Smith <[hidden email]> wrote: >> Gary - >> >> I *patently don't* recommend my method, though it does have some >> charms. I recently was faced with a similar problem to yours where I >> needed to cut and install trim around the perimeter of the room (with >> door openings) I just layed hardwood floor in. >> >> Rather than go into it in detail (I already did that and realized it was >> a TL;DR as usual, so cut it) I will just say that I approach these >> problems as *satisficing* and *constraint* problems rather than >> *optimization*. Once I had a candidate layout, I simply looked at the >> results and determined that the *waste* was acceptable. Depending on >> the circumstances I sometimes prefer to have for example, 2 3' leftovers >> rather than 1 5' leftover, other times, vice-versa, depending on how I >> might use said leftovers in some future application (or hedging against >> a mistake in my measuring/cutting). >> >> Care to share what your actual conduit/pipe project is? >> >> - Steve >> >> >>> Thanks for the links, Peter. I will probably use that software or >>> similar, to get a quick solution, then look at the MOOCs. >>> >>> On Fri, Sep 20, 2019 at 2:52 PM Pieter Steenekamp >>> <[hidden email]> wrote: >>>> Two possible approaches are: >>>> a) Solve the problem yourself. Use one or a combination of standard algorithms ( eg you mentioned linear programming and greedy algorithms, there are many more of course) and/or your own custom algorithm. If you wish to go this route and want to learn about the subject, I recommend the series of MOOCS by Stanford's Tim Roughgarden https://www.coursera.org/specializations/algorithms >>>> Or, I think yours is probably a knapsack -type problem and the MOOC https://www.coursera.org/learn/discrete-optimization covers that relatively well. >>>> b) But if you just want to get the solution you can use optimization software like https://www.ibm.com/za-en/products/ilog-cplex-optimization-studio (they have a free edition that will be good enough for your application) will solve it for you without you necessarily knowing how the software does it. >>>> >>>> On Fri, 20 Sep 2019 at 21:00, Gary Schiltz <[hidden email]> wrote: >>>>> I'd like advice on possible ways to solve the following problem >>>>> (plumbers must surely face this all the time). I need to cut a set of >>>>> metal tubes of varying lengths from standard length (6 meter) >>>>> galvanized conduit stock. The goal is to find the number of tubes I >>>>> need to buy, and the order of cuts to produce the minimum amount of >>>>> leftover, unused tube. I'm interested in what types of solutions >>>>> people use for similar 1-dimensional problems, e.g. linear >>>>> programming, greedy algorithms, etc. (I've been Googling). I'm only >>>>> looking to cut around 15-25 pieces, so my gut feeling is that an >>>>> exhaustive search of all possible solutions, though probably NP-hard, >>>>> would be feasible to perform. Working programs, as well as libraries >>>>> in any language would be a bonus. >>>>> >>>>> ============================================================ >>>>> FRIAM Applied Complexity Group listserv >>>>> Meets Fridays 9a-11:30 at cafe at St. John's College >>>>> to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com >>>>> archives back to 2003: http://friam.471366.n2.nabble.com/ >>>>> FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove >>>> ============================================================ >>>> FRIAM Applied Complexity Group listserv >>>> Meets Fridays 9a-11:30 at cafe at St. John's College >>>> to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com >>>> archives back to 2003: http://friam.471366.n2.nabble.com/ >>>> FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove >>> ============================================================ >>> FRIAM Applied Complexity Group listserv >>> Meets Fridays 9a-11:30 at cafe at St. John's College >>> to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com >>> archives back to 2003: http://friam.471366.n2.nabble.com/ >>> FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove >> >> ============================================================ >> FRIAM Applied Complexity Group listserv >> Meets Fridays 9a-11:30 at cafe at St. John's College >> to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com >> archives back to 2003: http://friam.471366.n2.nabble.com/ >> FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove > ============================================================ > FRIAM Applied Complexity Group listserv > Meets Fridays 9a-11:30 at cafe at St. John's College > to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com > archives back to 2003: http://friam.471366.n2.nabble.com/ > FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com archives back to 2003: http://friam.471366.n2.nabble.com/ FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove |
|
|
Welding galvanized steel without proper respirators (even outdoors) can kill you. Research this carefully.
How about some nice thick wall pvc? Carl On Fri, Sep 20, 2019, 17:48 Steven A Smith <[hidden email]> wrote: Gary - ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com archives back to 2003: http://friam.471366.n2.nabble.com/ FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove |
|
|
You can splice together conduit pieces with set screw couplers. They're cheap, stable under compression loads, only require a screwdriver to operate, and produce no toxic gases. -- rec -- On Fri, Sep 20, 2019 at 8:00 PM Carl Tollander <[hidden email]> wrote:
============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com archives back to 2003: http://friam.471366.n2.nabble.com/ FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove |
|
|
In reply to this post by Carl Tollander
Then there are those carefully selected branches from small trees
or large bushes that can be trimmed to size... watch out for
poison oak! On 9/20/19 7:59 PM, Carl Tollander
wrote:
============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com archives back to 2003: http://friam.471366.n2.nabble.com/ FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove |
|
|
In reply to this post by Steve Smith
Gary, Thanks for posing this problem to the group - it's been fun to have in the back of the mind for a day. I agree with Pieter that this is a kind of knapsack problem for which Dynamic Programming is a popular approach where you would extend to multiple knapsacks. I might approach it with a variant of the multiple traveling salesman (mTSP) problem where your purchased tubes are salesman and the tubes you want cut are cities which all need to be visited once with the constraint to minimize the number of salesmen and the upper bound on how far each salesman can travel (6 meters/miles). The difference of the tube cutting model with mTSP is that the tubes aren't in a spatial layout so you would use the length of the tube to be cut as the distance to visit that city. I like that the edges between tubes to be cut that tend to show up in successful solutions will get reinforced over time. Do you remember Alberto Gallo's model from Bios where he used ant colony optimization to solve the problem? A GA could also be used by indexing the tubes to be cut as genes in the genome. Owen has an elegant optimization on the TSP in Agentscript just using random swaps based on a fitness function - a kind of simulated annealing heuristic. http://agentscript.org/models/travsalesman.html Another approach would be a market model where 6m tubes bid on tubes segments and their value determined by how much a given tube would complete their unclaimed space. This was similar to Dick Gordon's paint booth problem at Bios bidding on cars to paint based on the cost of changing colors. Stephen -Stephen On Fri, Sep 20, 2019, 5:48 PM Steven A Smith <[hidden email]> wrote: Gary - ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com archives back to 2003: http://friam.471366.n2.nabble.com/ FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove |
|
|
Gary, If you want a quick answer to get your task done, I found a few online tools to calculate for you. eg: https://www.kurraglenindustries.com.au/linear-cutting-list-calculator.htm Then to study the problem later, it looks like your problem is well-known as the one-dimensional cutting stock problem and is NP-Hard. It's also equivalent to the bin packing problem. There's quite a few papers applying Ant colony optimization (ACO) as a successfu heuristic to both problems. And by golly, there's an extension to the cutting stock problem that involves welding :-) On Sat, Sep 21, 2019 at 8:59 PM Stephen Guerin <[hidden email]> wrote:
============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com archives back to 2003: http://friam.471366.n2.nabble.com/ FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove |
|
|
While the online don't list their optimization approaches, I suspect they use a simple approximation algorithm instead of a complicated heuristic algorithm. On the bin packing problem, a successful approximation is called "First Fit Decreasing" which is:
There's been a bit of research on the upper bound of the error of this approximation. If OPT = the optimal found by brute force search, "first fit decreasing" is guaranteed to be no worse than 11/9 * OPT + 6/9 On Sun, Sep 22, 2019 at 4:26 AM Stephen Guerin <[hidden email]> wrote:
============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com archives back to 2003: http://friam.471366.n2.nabble.com/ FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove |
«
Return to Friam
|
1 view|%1 views
| Free forum by Nabble | Edit this page |