Linear Cut Optimization Algorithm

[kaylab]

Does anyone know where I can find the source code or formula / algorithm to determine the optimal linear cuts, ie the least amount of material wasted ?

For example I have in stock
20 boards at 144"
20 boards at 132"
20 boards at 120"
20 boards at 108"
20 boards at 96"
20 boards at 84"
20 boards at 72"
20 boards at 60"
20 boards at 48"

I need
3 boards @ 17"
17 boards @ 39"
14 boards @ 81"
6 boards @ 113"

[Rod]

It has been discussed but I can't find it. The initial part of the solution is the knapsack problem and I can't find that either! Anyone else?

[metro]

AI: Knapsack problem was on the old forum created by bluatigro and last post by Anatoly August 9th 2016.
the page needed "indexbddf-2.html" which I do not seem to have for some reason

Maybe Anatoly has the code...

[Rod]

Ok, justbasiccom.proboards.com/thread/563/knapsack-problem-1-rosetta-code

' Knapsack problem/0-1 Revised again 2020-10-15.txt b+
' http://rosettacode.org/wiki/Knapsack_problem/0-1
' Found Knapsack problem posed by bluatigro and fixed 2016-07-23 at old JB Forum.
' This code follows that fixed method
' 2020-10-15 revised again because of a base 0, base 1 mixup code was doing 2X's as many calculations as needed.

maxWeight = 400 'for problem
maxItems = 22 'for data reading and array dimensions 8,388,608 combinations!
topItemsIndex = maxItems - 1
DIM item$(topItemsIndex), w(topItemsIndex), v(topItemsIndex)
FOR i = 0 TO topItemsIndex
   READ i$, ww, vv
   item$(i) = i$: w(i) = ww: v(i) = vv
NEXT
topComboIndex = 2 ^ maxItems - 1
FOR combo = 0 TO topComboIndex
   testList$ = "": testValue = 0: testWeight = 0
   FOR power = 0 TO topItemsIndex
       IF combo AND 2 ^ power THEN
           IF testList$ = "" THEN testList$ = item$(power) ELSE testList$ = testList$ + CHR$(10) + item$(power)
           testValue = testValue + v(power)
           testWeight = testWeight + w(power)
       END IF
   NEXT
   IF testWeight <= maxWeight AND testValue >= MaxValue THEN
       MaxValue = testValue
       saveCombo = combo
       saveList$ = testList$
       saveWeight = testWeight
   END IF
   IF combo MOD 1000 = 0 THEN LOCATE 1, 1: PRINT SPACE$(20): LOCATE 1, 1: PRINT combo 'progress
NEXT
CLS
PRINT "Best value found <= "; maxWeight; " was:"
PRINT saveList$
PRINT: PRINT "Total weight: "; saveWeight; "  Total value: "; MaxValue
print "Note: ";topComboIndex + 1;" combinations processed."

DATA "map",9,150
DATA "compass",13,35
DATA "water",153,200
DATA "sandwich",50,160
DATA "glucose",15,60
DATA "tin",68,45
DATA "banana",27,60
DATA "apple",39,40
DATA "cheese",23,30
DATA "beer",52,10
DATA "suntan cream",11,70
DATA "camera",32,30
DATA "T-shirt",24,15
DATA "trousers",48,10
DATA "umbrella",73,40
DATA "WP_trousers",42,70
DATA "WP_wear",43,75
DATA "note-case",22,80
DATA "sunglasses",7,20
DATA "towel",18,12
DATA "socks",4,50
DATA "book",30,10

' Output:
' Best value found <= 400 was:
' map
' compass
' water
' sandwich
' glucose
' banana
' suntan cream
' WP_trousers
' WP_wear
' note-case
' sunglasses
' socks
'
' Total weight: 396  Total value: 1030
' Note: 4194304 combinations processed.




However this takes a long time. I am thinking that we need to take each available length, knapsack it, sort into least waste order etc. Quite a problem.

[Rod]

Been playing. This is in no way the correct approach but you can see it gets a bit closer. 6x113,17 14x81,39 and 1x39,39,39 gets the cuts. You can see the answer but still lots to do to extract it from the list. And I repeat, not an optimal solution, just a practical hint.

I added to this it now attempts to produce a cutting list but fails to be optimal getting the last 39 cuts. I hope a maths guru jumps in with a real linear solution.

'load stock
dim stk(9,2)
stkL=1
stkN=2
stkM=9
for n= 1 to stkM
   read np,pl
   stk(n,stkL)=pl
   stk(n,stkN)=np
next

'load cuts
dim cut(4,2)
cutL=1
cutN=2
cutM=4
for n= 1 to cutM
   read np,pl
   cut(n,cutL)=pl
   cut(n,cutN)=np
next

'create cut patterns
dim pat(100,5)
cutL=1
cut1=2
cut2=3
cut3=4
cut4=5
pat=1

'create single cut patterns
for n= 1 to 4
   if l<=144 then
       pat(pat,cut1)=cut(n,cutL)
       pat(pat,cutL)=cut(n,cutL)
       pat=pat+1
   end if
next

'create two cut patterns
for n=1 to 4
   for m=1 to n
       l=0
       l=l+cut(n,cutL)+cut(m,cutL)
       if l<=144 then
           pat(pat,cut1)=cut(n,cutL)
           pat(pat,cut2)=cut(m,cutL)
           pat(pat,cutL)=l
           pat=pat+1
       end if
   next
next

'create three cut patterns
for n=1 to 4
   for m=1 to n
       for o=1 to m
           l=0
           l=l+cut(n,cutL)+cut(m,cutL)+cut(o,cutL)
           if l<=144 then
               pat(pat,cut1)=cut(n,cutL)
               pat(pat,cut2)=cut(m,cutL)
               pat(pat,cut3)=cut(o,cutL)
               pat(pat,cutL)=l
               pat=pat+1
           end if
       next
   next
next

'create four cut patterns
for n=1 to 4
   for m=1 to n
       for o=1 to m
           for p=1 to o
               l=0
               l=l+cut(n,cutL)+cut(m,cutL)+cut(o,cutL)+cut(p,cutL)
               if l<=144 then
                   pat(pat,cut1)=cut(n,cutL)
                   pat(pat,cut2)=cut(m,cutL)
                   pat(pat,cut3)=cut(o,cutL)
                   pat(pat,cut4)=cut(p,cutL)
                   pat(pat,cutL)=l
                   pat=pat+1
               end if
           next
       next
   next
next

'sort and display patterns
pat=pat-1
sort pat(,1,pat,cutL
for n= 1 to pat
   print "Pattern ";n;" ";pat(n,cut1);" ";pat(n,cut2);" ";pat(n,cut3);" ";pat(n,cut4);" ";pat(n,cutL)
next

'map cut pattern to available boards
dim map(200,3)
stkL=1
patN=2
wasT=3

map=1
for n=1 to pat
   for m=1 to 9
       map(map,patN)=n
       map(map,wasT)=stk(m,stkL)-pat(n,cutL)
       map(map,stkL)=stk(m,stkL)
       map=map+1
   next
next

'sort and display mapping
map=map-1
sort map(,1,map,wasT
for n=1 to map
   if map(n,wasT)>=0 and map(n,wasT)<10 then
       print "Mapping pattern ";map(n,patN);" to board ";map(n,stkL);" Waste ";map(n,wasT);
       print " Cuts ";pat(map(n,patN),cut1);" ";pat(map(n,patN),cut2);" ";pat(map(n,patN),cut3);" ";
       print pat(map(n,patN),cut4);" Length ";pat(map(n,patN),cutL)
   end if
next

'apply optimal cuts to request
restore
dim s(200)
for n= 1 to 9
   read np,pl
   s(pl)=np
next
dim c(200)
for n= 1 to 4
   read np,pl
   c(pl)=np
next

sort cut(,4,1,cutL
for cc=1 to 4
'find longest first
for n= 1 to map
   if map(n,wasT)>=0 and pat(map(n,patN),cut1)=cut(cc,cutL) then
       if c(pat(map(n,patN),cut1))<=s(map(n,stkL)) then
           s(map(n,stkL))=s(map(n,stkL))-c(pat(map(n,patN),cut1))
           boards=c(pat(map(n,patN),cut1))
       else
           boards=s(map(n,stkL))
           s(map(n,stkL))=0
       end if
       print boards;" lengths of Board ";map(n,stkL);
       for k=2 to 5
           print " Cut ";pat(map(n,patN),k);
           c(pat(map(n,patN),k))=c(pat(map(n,patN),k))-boards
           if c(pat(map(n,patN),k))<0 then c(pat(map(n,patN),k))=0
       next
       print
       exit for
   end if
next
next





wait



data 20,144
data 20,132
data 20,120
data 20,108
data 20,96
data 20,84
data 20,72
data 20,60
data 20,48

data 3,17
data 17,39
data 14,81
data 6,113



[Rod]

I had left out single cut patterns. I put it in the above code. It makes a difference. While it is not a linear solution it does marshal the options and lists just a few candidates to consider.

Now I would say the solution is:

3 x 132 boards cut at 113 and 17 wastage 6
3 x 120 boards cut at 113 wastage 21
14 x 120 boards cut at 81 and 39 wastage 0
1 x 120 board cut at 39,39,39 wastage 3

Total wastage 30!

Now if my program could just pull that out of the candidates!