<div dir="ltr"><div dir="ltr"><div>Algorithm with guaranteed optimal:</div><ol><li>purchase ceil(TotalLengthNeeded / 6)  tubes</li><li><a href="https://www.youtube.com/watch?v=ShByF_MBpNI" target="_blank">Weld purchased tubes into one long tube</a> *</li><li>Cut what you need in any order</li></ol><div>   * assumes welder $ < optimization design and compute time<br></div><div><div dir="ltr" class="m_5299573668508838392m_5870680348142992156gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr">_______________________________________________________________________<br><a href="mailto:stephen.guerin@simtable.com" target="_blank">Stephen.Guerin@Simtable.com</a><div>CEO, Simtable  <a href="http://www.simtable.com/" target="_blank">http://www.simtable.com</a><br><div>1600 Lena St #D1, Santa Fe, NM 87505<div><div>office: (505)995-0206 <span style="font-size:12.8000001907349px">mobile: (505)577-5828</span></div><div><span style="font-size:12.8000001907349px">twitter: @simtable</span></div><div></div></div></div></div></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, Sep 20, 2019 at 1:56 PM Gary Schiltz <<a href="mailto:gary@naturesvisualarts.com" target="_blank">gary@naturesvisualarts.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Thanks for the links, Peter. I will probably use that software or<br>
similar, to get a quick solution, then look at the MOOCs.<br>
<br>
On Fri, Sep 20, 2019 at 2:52 PM Pieter Steenekamp<br>
<<a href="mailto:pieters@randcontrols.co.za" target="_blank">pieters@randcontrols.co.za</a>> wrote:<br>
><br>
> Two possible approaches are:<br>
> 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 <a href="https://www.coursera.org/specializations/algorithms" rel="noreferrer" target="_blank">https://www.coursera.org/specializations/algorithms</a><br>
> Or, I think yours is probably a knapsack -type problem and the MOOC <a href="https://www.coursera.org/learn/discrete-optimization" rel="noreferrer" target="_blank">https://www.coursera.org/learn/discrete-optimization</a> covers that relatively well.<br>
> b) But if you just want to get the solution you can use optimization software like <a href="https://www.ibm.com/za-en/products/ilog-cplex-optimization-studio" rel="noreferrer" target="_blank">https://www.ibm.com/za-en/products/ilog-cplex-optimization-studio</a> (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.<br>
><br>
> On Fri, 20 Sep 2019 at 21:00, Gary Schiltz <<a href="mailto:gary@naturesvisualarts.com" target="_blank">gary@naturesvisualarts.com</a>> wrote:<br>
>><br>
>> I'd like advice on possible ways to solve the following problem<br>
>> (plumbers must surely face this all the time). I need to cut a set of<br>
>> metal tubes of varying lengths from standard length (6 meter)<br>
>> galvanized conduit stock. The goal is to find the number of tubes I<br>
>> need to buy, and the order of cuts to produce the minimum amount of<br>
>> leftover, unused tube.  I'm interested in what types of solutions<br>
>> people use for similar 1-dimensional problems, e.g. linear<br>
>> programming, greedy algorithms, etc. (I've been Googling). I'm only<br>
>> looking to cut around 15-25 pieces, so my gut feeling is that an<br>
>> exhaustive search of all possible solutions, though probably NP-hard,<br>
>> would be feasible to perform. Working programs, as well as libraries<br>
>> in any language would be a bonus.<br>
>><br>
>> ============================================================<br>
>> FRIAM Applied Complexity Group listserv<br>
>> Meets Fridays 9a-11:30 at cafe at St. John's College<br>
>> to unsubscribe <a href="http://redfish.com/mailman/listinfo/friam_redfish.com" rel="noreferrer" target="_blank">http://redfish.com/mailman/listinfo/friam_redfish.com</a><br>
>> archives back to 2003: <a href="http://friam.471366.n2.nabble.com/" rel="noreferrer" target="_blank">http://friam.471366.n2.nabble.com/</a><br>
>> FRIAM-COMIC <a href="http://friam-comic.blogspot.com/" rel="noreferrer" target="_blank">http://friam-comic.blogspot.com/</a> by Dr. Strangelove<br>
><br>
> ============================================================<br>
> FRIAM Applied Complexity Group listserv<br>
> Meets Fridays 9a-11:30 at cafe at St. John's College<br>
> to unsubscribe <a href="http://redfish.com/mailman/listinfo/friam_redfish.com" rel="noreferrer" target="_blank">http://redfish.com/mailman/listinfo/friam_redfish.com</a><br>
> archives back to 2003: <a href="http://friam.471366.n2.nabble.com/" rel="noreferrer" target="_blank">http://friam.471366.n2.nabble.com/</a><br>
> FRIAM-COMIC <a href="http://friam-comic.blogspot.com/" rel="noreferrer" target="_blank">http://friam-comic.blogspot.com/</a> by Dr. Strangelove<br>
<br>
============================================================<br>
FRIAM Applied Complexity Group listserv<br>
Meets Fridays 9a-11:30 at cafe at St. John's College<br>
to unsubscribe <a href="http://redfish.com/mailman/listinfo/friam_redfish.com" rel="noreferrer" target="_blank">http://redfish.com/mailman/listinfo/friam_redfish.com</a><br>
archives back to 2003: <a href="http://friam.471366.n2.nabble.com/" rel="noreferrer" target="_blank">http://friam.471366.n2.nabble.com/</a><br>
FRIAM-COMIC <a href="http://friam-comic.blogspot.com/" rel="noreferrer" target="_blank">http://friam-comic.blogspot.com/</a> by Dr. Strangelove<br>
</blockquote></div></div>