Results 1 to 3 of 3

Math Help - Applied Linear Programming

  1. #1
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    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)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Media_Man View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Linear programming help
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: May 16th 2009, 01:31 AM
  2. Linear programming
    Posted in the Advanced Applied Math Forum
    Replies: 3
    Last Post: January 4th 2009, 03:48 PM
  3. Replies: 1
    Last Post: November 17th 2008, 04:18 AM
  4. linear programming
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: May 25th 2008, 07:40 AM
  5. Linear Programming
    Posted in the Pre-Calculus Forum
    Replies: 5
    Last Post: May 6th 2008, 05:31 AM

Search Tags


/mathhelpforum @mathhelpforum