[FRIAM] Optimization problem

[Gary Schiltz]

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.