I am presented with a problem where I have to connect two points using pipes. I have an inventory of pipes with different lengths and I need to optimize the selection of the pipes to minimize the wasted pipes (more than the target) and to minimize joints between pipes.

I searched for algorithms for this problem and found the cutting stock algorithm which is basically the opposite of what I need to do. Are there any algorithms that deal with this type of problems? Any suggestions are appreciated.

CodePudding user response：

The "opposite" of the cutting stock problem is the bin packing problem (BPP) - though mathematically they are essentially the same. Also, in your case, you are allowed to exceed the capacity of the bin. The BPP can be formulated as a mixed integer linear program (MILP) and solved by a MILP solver like CBC, CPLEX, Gurobi, etc. There are also various heuristics available, which will find at least a good solution.

Note that considering offcuts longer than 0.5 as not waste will likely lead to an accumulation of short pieces. That will increase the number of joins, and hence cost, later. i.e. a short-term optimal solution may not be optimal in the long term.