For developers
Het 1D-snijprobleem
Hoe een set van vereiste lengtes te zagen uit handelslengtes met gebruik van zo min mogelijk staven, dat is het 1D-snijprobleem: een klassiek, echt moeilijk optimalisatieprobleem. Hier is wat het is, waarom het zich niet laat forceren, en hoe het in de praktijk wordt opgelost, inclusief in de API achter deze site.
Wat het 1D-snijprobleem is
U krijgt handelslengtes van een vaste maat (bijvoorbeeld staven van 6000 mm) en een lijst van benodigde delen, elk met een lengte en een hoeveelheid. Een zaagpatroon is één manier om een enkele handelslengte in een aantal van die delen te verzagen; wat overblijft is afval. Het probleem is om patronen te kiezen, en te bepalen hoeveel staven volgens elk patroon te verzagen, zodat elk benodigd deel wordt geproduceerd en het totale aantal handelslengtes, of equivalent het totale afval, zo klein mogelijk is. Eén dimensie, omdat alleen de lengte telt: het zaagblad gaat door de hele dwarsdoorsnede, dus breedte en profiel spelen geen rol in de puzzel.
1D-bakkenprobleem, en waarom het NP-moeilijk is
Het snijprobleem is een veralgemening van het 1D-bakkenprobleem: het bakkenprobleem vraagt u een set items van verschillende grootte in zo min mogelijk bakken van vaste grootte te passen. Het snijprobleem is dezelfde vraag wanneer items in grote hoeveelheden herhaald worden, zodat u redeneert over patronen in plaats van individuele items. Het bakkenprobleem is een van de klassieke NP-moeilijke problemen, en de beslissingsvorm, passen deze items in k bakken, is NP-compleet. Het snijprobleem erft die moeilijkheidsgraad.
De reden is de combinatorische explosie. Het aantal verschillende zaagpatronen groeit exponentieel met het aantal deelgroottes, en het aantal manieren om hoeveelheden over die patronen te verdelen explodeert daarbovenop. Er is geen bekend algoritme dat het gegarandeerde optimum vindt in een tijd die polynomiaal schaalt met de input, en tenzij P gelijk is aan NP, zal er ook geen komen. Echte oplossers sommen dus niet alles op; ze zijn slim in welke mogelijkheden ze kunnen uitsluiten.
Hoe het in de praktijk wordt opgelost
First-fit-decreasing (FFD)
De werkpaard-heuristiek: sorteer de benodigde delen van langst naar kortst, plaats dan elk deel op de eerste staaf waar het nog past, en begin alleen een nieuwe staaf als er nergens meer ruimte is. Het is snel en verrassend goed, bewijsbaar binnen ongeveer 11/9 van het optimale aantal staven plus een kleine constante. De meeste tools stoppen hier; een goede gebruikt FFD als startpunt, niet als eindstreep.
Kolomgeneratie (Gilmore en Gomory)
De formulering die grote vraagstukken behapbaar maakte. Gilmore en Gomory (1961) beschreven het probleem met één variabele per zaagpatroon en, aangezien er exponentieel veel zijn, losten ze de lineaire relaxatie op door vertraagde kolomgeneratie: begin met een handvol patronen en genereer herhaaldelijk het volgende meest nuttige patroon door een begrensd knapzak-subprobleem op te lossen. De ondergrens die dit oplevert is beroemd strak.
Branch-and-bound en branch-and-price
Om die fractionele relaxatie om te zetten in een heel aantal staven moet je zoeken, maar niet blindelings. Branch-and-bound verkent de boom van integer-keuzes en gebruikt de LP-grens om hele takken te snoeien die het beste tot nu toe gevonden plan niet kunnen verslaan; gecombineerd met kolomgeneratie wordt dit branch-and-price, de basis van de meeste exacte snijprobleem-oplossers.
Ondergrenzen, en een bewijs
Een serieuze oplosser geeft niet zomaar een plan, het berekent een ondergrens (van de LP-relaxatie, of een eenvoudiger argument op basis van de totale lengte) en vergelijkt. Wanneer een plan precies evenveel staven gebruikt als de ondergrens bewijst dat onvermijdelijk is, is het plan bewijsbaar optimaal: geen enkel plan kan beter, en de oplosser kan dit bevestigen in plaats van te hopen op een toevalstreffer.
Hoe LinearCutting het oplost
LinearCutting gebruikt deze aanpak: een snelle heuristiek voor een onmiddellijk uitvoerbaar plan, daarna een ondergrens-gestuurde zoektocht die blijft verbeteren tot het ofwel de ondergrens evenaart (bewijsbaar optimaal, en meldt dat ook) of zijn tijdsbudget opgebruikt en het beste gevonden plan retourneert. Het modelleert ook de fysica: zaagsnedebreedte bij elke snede, afkorten van het uiteinde, reststukken van vaste hoeveelheid en schuine sneden die extra materiaal verbruiken. Een plan dat geen rekening houdt met het zaagblad is niet alleen suboptimaal, het is fout. De benchmark-opdrachten zijn gepubliceerd zodat u de resultaten kunt vergelijken met elk ander gereedschap.
Het wordt aangeboden als een JSON API: stuur uw onderdelen en voorraad, en krijg een geverifieerd zaagplan terug met de lay-outs, het afval, het aantal instellingen en of het plan de optimale grens heeft bereikt. Er zijn officiële clients voor Python (pip install linearcutting) en JavaScript of TypeScript (npm install linearcutting), dus het aanroepen ervan is een paar regels in beide talen.
Los het op vanuit uw code
Schrijf zelf geen oplosser, maar roep er een aan. Dezelfde engine achter de calculator van deze site is een JSON API met officiële Python- en JavaScript-clients, een gratis openbaar niveau en een live voorbeeld dat u in de documentatie kunt uitvoeren.
pip install linearcutting npm install linearcutting