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
