1. ## Applied Linear Programming

Warning: This is a very long and involved problem. I am going to present the problem in bite-size pieces.

One of my clients is an engineering firm that builds overhead bridge cranes. After designing a project on AutoCAD, the engineers compile a list of specific lengths of steel they need. They then place an order with a steel supplier and begin building. The problem is, suppliers only sell steel in specific pre-cut lengths, so they must order enough to cover the project and cut the pieces they need in-house. Say they need 19 3ft pieces (57ft total), but the supplier only sells 10ft pieces. They actually have to buy 70ft worth of steel, not 60. Reason: they can only cut 3 usable 3ft pieces out of a given 10ft piece, leaving 1ft of scrap. Therefore, they must buy ceil(19/floor(10/3)) pieces of steel, leaving 13ft of scrap. Assuming that welding scrap pieces together is out of the question for structural reasons, the task now becomes: Given a manifest of required lengths {L1,L2,L3,…,Ln} in quantities {Q1,Q2,Q3,…,Qn} when the supplier only sells in lengths {A1,A2,…Am}, design an algorithm that returns a purchase order and cutting instructions such that scrap is minimized.

I have made a lot of progress on this and I HAVE DESIGNED A WORKING PROGRAM. It is just horribly inefficient. Using linear Diophantine equations, the program creates a loop to test hundreds of thousands of “candidate” arrangements, pausing at each solution and asking the user if the scrap is acceptable. The runtime is exponential and certain inputs stall it out entirely because the number of candidates is too large. Embarrassingly, “good” arrangements can be found by hand for small orders, but a program’s job of course is to find mathematically “best” solutions. I do not believe this is an NP problem, but I have yet to find a polynomial-time algorithm for it, despite being able to easily solve small manifests by hand.

I’ve made plenty of progress and looked at this from several angles, so I won’t list them all here, but here are some nuggets to get you started. I suggest you start by verifying these observations for yourself:

Total required length T=L1*Q1 + L2*Q2 + … + Ln*Qn
Total ordered length must be a multiple of G=gcd(A1,A2,…,Am)
Therefore the minimum possible scrap is G-T%G
Provided that for each L, there exists an A>L, a solution is guaranteed to exist (however inefficient).
Sample data: L={356.5”,239”,220.5”,206”,148” }, Q={4,4,4,4,2}, A={30’,40’,55’}
Solution:
Qty 2 Cut 02000 From 40’ Drop 1.875”
Qty 4 Cut 10000 From 30’ Drop 3.5”
Qty 2 Cut 00011 From 30’ Drop 5.875”
Qty 2 Cut 00210 From 55’ Drop 1.75”
-Ver Sum 44442 Tot Cut 365’4” Buy 2-55’ 2-40’ 6-30’ Tot 370’ Scrap 4’7” (1.24% Waste)

2. Originally Posted by Media_Man
Warning: This is a very long and involved problem. I am going to present the problem in bite-size pieces.

One of my clients is an engineering firm that builds overhead bridge cranes. After designing a project on AutoCAD, the engineers compile a list of specific lengths of steel they need. They then place an order with a steel supplier and begin building. The problem is, suppliers only sell steel in specific pre-cut lengths, so they must order enough to cover the project and cut the pieces they need in-house. Say they need 19 3ft pieces (57ft total), but the supplier only sells 10ft pieces. They actually have to buy 70ft worth of steel, not 60. Reason: they can only cut 3 usable 3ft pieces out of a given 10ft piece, leaving 1ft of scrap. Therefore, they must buy ceil(19/floor(10/3)) pieces of steel, leaving 13ft of scrap. Assuming that welding scrap pieces together is out of the question for structural reasons, the task now becomes: Given a manifest of required lengths {L1,L2,L3,,Ln} in quantities {Q1,Q2,Q3,,Qn} when the supplier only sells in lengths {A1,A2,Am}, design an algorithm that returns a purchase order and cutting instructions such that scrap is minimized.

I have made a lot of progress on this and I HAVE DESIGNED A WORKING PROGRAM. It is just horribly inefficient. Using linear Diophantine equations, the program creates a loop to test hundreds of thousands of candidate arrangements, pausing at each solution and asking the user if the scrap is acceptable. The runtime is exponential and certain inputs stall it out entirely because the number of candidates is too large. Embarrassingly, good arrangements can be found by hand for small orders, but a programs job of course is to find mathematically best solutions. I do not believe this is an NP problem, but I have yet to find a polynomial-time algorithm for it, despite being able to easily solve small manifests by hand.

Ive made plenty of progress and looked at this from several angles, so I wont list them all here, but here are some nuggets to get you started. I suggest you start by verifying these observations for yourself:

Total required length T=L1*Q1 + L2*Q2 +  + Ln*Qn
Total ordered length must be a multiple of G=gcd(A1,A2,,Am)
Therefore the minimum possible scrap is G-T%G
Provided that for each L, there exists an A>L, a solution is guaranteed to exist (however inefficient).
Sample data: L={356.5,239,220.5,206,148 }, Q={4,4,4,4,2}, A={30,40,55}
Solution:
Qty 2 Cut 02000 From 40 Drop 1.875
Qty 4 Cut 10000 From 30 Drop 3.5
Qty 2 Cut 00011 From 30 Drop 5.875
Qty 2 Cut 00210 From 55 Drop 1.75
-Ver Sum 44442 Tot Cut 3654 Buy 2-55 2-40 6-30 Tot 370 Scrap 47 (1.24% Waste)
Cutting Stock Problem?

CB

3. ## Eureka!

Brilliant! Yes, that is correct. A one-dimensional packing problem. Does anyone know of a resource that can walk me through an algorithm. Apparently, this is NP-complete after all