Linear optimization of profile cutting

[angelo2449]

Hi guys,

has anyone already written a routine for linear optimization of a profile?

I'll explain :

I have 6500 mm profiles. and many different cutting measures.

The problem is to organize the cuts to make the most of the profiles.

Thank you.

[Rod]

Well see if this helps but you will need to puzzle it out. It gets fed the stock lengths available and then the number and length of the desired cuts. It then list the possible outcomes showing the waste.

Shout if you get stuck and give us an example of what your stock is and cuts are.

'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  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







Been discussed before libertybasiccom.proboards.com/thread/1540/linear-cut-optimization-algorithm

[angelo2449]

Thanks Rod,
this is a topic I have never addressed.
I trust in your precious help, I attach the example of my problem:
This is an example of the file, the records are separated by the double line.
The data is divided by in '#'.
The first data is the name of the element.
The second data is the length of the element.
The third data is the number of elements.
Dimensions are in mm.
In reality, the records will be more numerous.
The problem lies in arranging the elements in 6500 mm. bars. in order to have less waste ever.
What do you say?
Thank you.

TelOri#1044#2
TelVert#1544#2
AntaBaseOri#960#4
AntaBaseVert#1460#4
FermaOri#871#4
FermaVert#1327#4
===================
TelOri#1155#2
TelVert#1574#2
AntaBaseOri#980#4
AntaBaseVert#1565#4
FermaOri#880#4
FermaVert#1359#4
===================
TelOri#1064#2
TelVert#1544#2
AntaBaseOri#960#4
AntaBaseVert#1460#4
FermaOri#851#4
FermaVert#1400#4
===================
TelOri#1044#2
TelVert#1595#2
AntaBaseOri#1010#4
AntaBaseVert#1460#4
FermaOri#861#4
FermaVert#1437#4
===================

[angelo2449]

Greetings,

I wrote this simplified cut optimization procedure.

It works great.


insert code here

' @[Rileva]

' @[Calcola]

' @[Secondo_Giro]

' @[Reset]



on error goto [GestErr]



dim Linea$(100), Riga$(100), BarraX$(100), Barra$(100), Qta$(100)



Lama = 10 : Barra = 6500 : Cont= 0



Caso$ = "Telaio"

gosub [Reset]

gosub [Rileva]



if Cont > 0 then

print "Telaio"

print "Lunghezza Tot mm. "; Lung

print

gosub [Calcola]



NumBarre = Lung / Barra



Frac = NumBarre - int(NumBarre)



if Frac > 0 then

NumBarre = int(NumBarre) + 1

end if



print "Numero Barre per Telaio N. "; NumBarre

Usato = Lung + Tagliato

print "Usato mm. "; Usato

print

print "======================================"



end if



' ------------------------------



Caso$ = "Anta"

gosub [Reset]

gosub [Rileva]



if Cont > 0 then

print "Anta"

print "Lunghezza Tot mm. "; Lung

print

gosub [Calcola]



NumBarre = Lung / Barra



Frac = NumBarre - int(NumBarre)



if Frac > 0 then

NumBarre = int(NumBarre) + 1

end if



print "Numero Barre per Ante N. "; NumBarre

Usato = Lung + Tagliato

print "Usato mm. "; Usato



print

print "======================================"



end if



' ------------------------------



Caso$ = "FermaVetro"

gosub [Reset]

gosub [Rileva]



if Cont > 0 then

print "FermaVetro"

print "Lunghezza Tot mm. "; Lung

print

gosub [Calcola]



NumBarre = Lung / Barra



Frac = NumBarre - int(NumBarre)



if Frac > 0 then

NumBarre = int(NumBarre) + 1

end if



print "Numero Barre per FermaVetro N. "; NumBarre

print "Numero Barre per Ante N. "; NumBarre

Usato = Lung + Tagliato

print "Usato mm. "; Usato



print

print "======================================"



end if



end



' -------------------------------------------------



' @[Rileva]



[Rileva]



open "D:\AltProvvisori\Profili.txt" for input as #1

while eof(#1) = 0

input #1, StringaIn$



Pos1 = instr(trim$(StringaIn$), "#", 1)

Pos2 = instr(trim$(StringaIn$), "#", Pos1 + 1)

Pos3 = instr(trim$(StringaIn$), "#", Pos2 + 1)

Nome$ = mid$(StringaIn$, Pos1 + 1, Pos2 - Pos1 - 1)

Dato$ = mid$(StringaIn$, Pos2 + 1, Pos3 - Pos2 - 1)

Qta$ = mid$(StringaIn$, Pos3 + 1)



select case Caso$



case "Telaio"

if Nome$ = "TelOri" or Nome$ = "TelVert" then

Lu = (val(Dato$) * val(Qta$))

Lung = Lung + Lu

Cont = Cont + 1

Riga$(Cont) = StringaIn$

end if



case "Anta"

if Nome$ = "AntaOri" or Nome$ = "AntaVert" then

Lu = (val(Dato$) * val(Qta$))

Lung = Lung + Lu

Cont = Cont + 1

Riga$(Cont) = StringaIn$

end if



case "FermaVetro"

if Nome$ = "FermaOri" or Nome$ = "FermaVert" then

Lu = (val(Dato$) * val(Qta$))

Lung = Lung + Lu

Cont = Cont + 1

Riga$(Cont) = StringaIn$

end if



end select



wend

close #1



return ' fine [Rileva]



' ----------------------------------------------



' @[Calcola]



[Calcola]



print "Cont "; Cont



for u = 1 to Cont



Pos1 = instr(trim$(Riga$(u)), "#", 1)

Pos2 = instr(trim$(Riga$(u)), "#", Pos1 + 1)

Pos3 = instr(trim$(Riga$(u)), "#", Pos2 + 1)

Num$ = left$(Riga$(u), Pos1 - 1)

Nome$ = mid$(Riga$(u), Pos1 + 1, Pos2 - Pos1 - 1)

Dato$ = mid$(Riga$(u), Pos2 + 1, Pos3 - Pos2 - 1)

Qta$(u) = mid$(Riga$(u), Pos3 + 1)



Somma1 = Somma1 + val(Dato$)



select case



case (Somma1 = Barra)

Barra$ = Dato$



case (Somma1 < Barra)

Barra$ = Barra$ + "-" + Dato$ + "-"

BarraN$ = BarraN$ + "-" + str$(u) + "-"

Sq$ = Sq$ + "-" + Qta$(u) + "-"

Ta = Ta + 1



case (Somma1 > Barra)

Somma1 = Somma1 - val(Dato$)

x = x + 1

Linea$(x) = Riga$(u)



end select



next u



if Somma1 > 0 then

print "Caso = "; Caso$

print "Barra$ "; Barra$; " Somma1 mm. "; Somma1

print "BarraN$ "; BarraN$

print "Quantita "; Sq$

Scarto = Barra - Somma1

print "Scarto mm. "; Scarto; " per Barra"

Ta = Ta + 1

print "Tagli "; Ta; " - Tagliato mm. "; Ta * Lama

print

Sq$ = ""

end if



' -------------------------------------------



if x > 0 then

Barra$ = "" : BarraN$ = ""

Somma1 = 0 : Ta = 0

y = 0

gosub [Secondo_Giro]



if Somma1 > 0 then

print "Caso = "; Caso$

print "Barra$ "; Barra$; " Somma1 mm. "; Somma1

print "BarraN$ "; BarraN$

print "Quantita "; Sq$

Scarto = Barra - Somma1

print "Scarto mm. "; Scarto; " per Barra"

Ta = Ta + 1

print "Tagli "; Ta; " - Tagliato mm. "; Ta * Lama

print

x = 0 : Sq$ = ""

end if

end if



' -------------------------------------------



while y > 0

x = y

Ta = 0 : Somma1 = 0

Barra$ = "" : BarraN$ = "" : y = 0

gosub [Secondo_Giro]



if Somma1 > 0 then

print "Caso = "; Caso$

print "Barra$ "; Barra$; " Somma1 mm. "; Somma1

print "BarraN$ "; BarraN$

print "Quantita "; Sq$

Scarto = Barra - Somma1

print "Scarto mm. "; Scarto; " per Barra"

Ta = Ta + 1

print "Tagli "; Ta; " - Tagliato mm. "; Ta* Lama

print

Sq$ = ""

end if

wend



' --------------------------------------------



' @[Secondo_Giro]



[Secondo_Giro]



for u = 1 to x



Pos1 = instr(trim$(Linea$(u)), "#", 1)

Pos2 = instr(trim$(Linea$(u)), "#", Pos1 + 1)

Pos3 = instr(trim$(Linea$(u)), "#", Pos2 + 1)

Num$ = left$(Linea$(u), Pos1 - 1)

Nome$ = mid$(Linea$(u), Pos1 + 1, Pos2 - Pos1 - 1)

Dato$ = mid$(Linea$(u), Pos2 + 1, Pos3 - Pos2 - 1)

Qta$(u) = mid$(Linea$(u), Pos3 + 1)



Somma1 = Somma1 + val(Dato$)



select case



case (Somma1 = Barra)

Barra$ = Dato$



case (Somma1 < Barra)

Barra$ = Barra$ + "-" + Dato$ + "-"

BarraN$ = BarraN$ + "-" + str$(u) + "-"

Sq$ = Sq$ + "-" + Qta$(u) + "-"

Ta = Ta + 1



case (Somma1 > Barra)

Somma1 = Somma1 - val(Dato$)

y = y + 1

Linea$(y) = Linea$(u)



end select



next u



return



return



' ------------------ fine [Calcola]



' @[Reset]



[Reset]



Lung = 0 : Cont = 0 : Somma1 = 0

Barra$ = "" : BarraN$ = ""

Usato = 0 : Usato1 = 0 : Usato2 = 0 : NumBarre = 0 : Tagliato = 0

Maggiore = 0 : Minore = 0 : Ta = 0



for r = 1 to 100

Riga$(r) = ""

Linea$(r) = ""

next r



return



' ------------------



[GestErr]



print Err$



wait



' ------------------


The input data are:
1#TelOri#1044#1

1#TelOri#1544#2

1#TelVert#1844#1

2#TelVert#2544#1

2#TelVert#1644#1

2#TelVert#2344#1

2#TelOri#1044#1

3#TelVert#2644#1

3#TelVert#2144#1

3#TelOri#644#1

3#TelOri#844#1

4#AntaOri#1000#1

4#AntaVert#1000#1

5#AntaOri#1500#4

5#AntaVert#1500#4

6#AntaVert#1100#3

[honkytonk]

Hello "angelo2449"
Your explanation is not clear to me.
What do you want to do at the end ?

[Rod]

At the end Angelo hopes to have used much less stock than previously. I was thinking that any solution must feed back in unused stock. But I have not had time to think it through.

If you look at the Rosetta code story you will see that it is quite a hard problem to “solve” and who knows if you have the optimum solution.

But if you save ten lengths of stock a day compared to previous days it does not really need to be an optimum solution.

[honky]

As identical names have different variables, I propose to put all of this in an texteditor.
With in the first line: Names, Structure A, Structure B; Structure C ... ect ... (which can be above the texteditor).
And on the following lines;
Name-X variable A variable B variable C ... ect
Name-Y variable A variable B variable C ... ect
... ect ...
With automatic tabs.