<div dir="ltr">Two possible approaches are:<div>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">https://www.coursera.org/specializations/algorithms</a></div><div>Or, I think yours is probably a knapsack -type problem and the MOOC <a href="https://www.coursera.org/learn/discrete-optimization">https://www.coursera.org/learn/discrete-optimization</a> covers that relatively well.</div><div>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">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. </div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, 20 Sep 2019 at 21:00, Gary Schiltz <<a href="mailto:gary@naturesvisualarts.com">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">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>
</blockquote></div>