Welk algoritme kiezen?

[P_Tingen]

Voor het bedrijf waar ik werk moeten we het bestaande proces van het maken van werkorders optimaliseren. Ik zal in korte lijnen schetsen wat het probleem is.

We hebben meerdere pakhuizen waar onze grondstof (tabak) ligt opgeslagen. Op het moment dat de tabak in balen of kisten binnenkomt, wordt het geanalyseerd op een aantal belangrijke eigenschappen zoals nicotinegehalte, suikers, kwaliteit, aanwezigheid van kevers en meer van dat soort dingen.

De aard van de tabak (soort tabak, manier van drogen, herkomst) bepaalt de tabaksklassse. Dit zijn min of meer gestandaardiseerde groepen van tabak. Een tabak valt altijd in één klasse.

De tabak zoals die in sigaretten en shag zit noemen we een blend. Een blend bestaat uit een aantal tabaksklasses. Hier zijn recepten voor waarbij bekend is dat er x% van klasse A in een blend moet, y% van klasse B en z% van klasse C. Het aantal klassen per blend varieert van 4 tot 20, maar de meesten hebben 8-12 klassen. Er zijn nog allerlei extra randvoorwaarden zoals mogelijke vervangingen van klasses (bv: als klasse A er niet is, gebruik dan klasse B, of gebruik klasse C en D in een verhouding van 40-60%). Die laat ik hier even buiten beschouwing.

Ik kom nu bij het probleem, want om een werkorder te maken voor een blend, moet ik eerst kijken welke klassen daarin moeten en vervolgens kijken naar wat ik op voorraad heb per klasse. Er wordt een soort 'default' werkorder gemaakt, die puur op basis van FIFO, prioriteiten en blokkades tabaksbalen selecteert. Vervolgens wordt deze order doorgerekend om te zien of deze voldoet aan de eisen. Op dit moment wordt er vooral gekeken naar nicotine. Per blend ligt vast tussen welke grenzen de nicotine moet zitten, maar er zijn ook grenzen voor bijvoorbeeld suikers. In de meeste gevallen voldoen de default order dan ook niet en moeten er tabaksbalen worden gewisseld voor een ander om een correcte blend te maken. De huidige oplossing is een min of meer brute force aanpak waarbij alle mogelijke combinaties een voor een worden bekeken tot er een combinatie uitrolt die voldoet aan de eisen. Als je bedenkt dat een gemiddelde blend bestaat uit 10 klassen en er gemiddeld 10 tabaksbalen per klasse op voorraad liggen, dan betekent dat 10 ^ 10 combinaties van tabaksbalen. Da's een beetje veul om allemaal door te rekenen. In het verleden is er al wat geoptimaliseerd aan het proces maar de rek is er wel uit. Bovendien willen we op meer criteria kunnen selecteren dan alleen nicotine, dus het moet op de schop.

Maar we zijn vast niet de eersten die een probleem als dit moeten tackelen. Het probleem is alleen: hoe heet mijn probleem of hoe heet het algoritme dat ik zoek? Ik heb al wat gezocht en kwam onder andere een pagina tegen met de meest gebruikte algoritmes voor data mining maar daar heb ik in zoverre nog niet zoveel aan. Ik vraag me ook af of mijn probleem een data mining probleem is of een optimalisatieprobleem, maar ik zou wat goede handvatten kunnen gebruiken.

[justahuman]

Klinkt als een variantie op het Continuous knapsack problem, nadeel is dat hier niet echt een snel algoritme voor bestaat.

[sinasappel]

Dit kun je toch gewoon doen met een Excel solver? En als je je daar een beetje in verdiept kun je het zelfs automatiseren.

[Florian]

Misschien kan je de simplex methode gebruiken. Met het simplex algoritme kan je een doelfunctie in combinatie met randvoorwaarde optimaliseren. Je hebt dus een optimalisatieprobleem.

[P_Tingen]

Ik ben aan het experimenteren met de Excel solver. Die ziet er op zich wel bruikbaar uit. Nog wel even kijken of ik vanuit onze applicatie gemakkelijk kan im- en exporteren naar de solver. En hoe snel hij is met grotere sets. Tot nu heb ik met een relatief kleine set gespeeld.

[H!GHGuY]

Ik dacht eerder aan een flow network met daarop de bijpassende algoritmes. Maar zoek je er ook niet suf op, want ik kan er bij deze best naast zitten of dit optimaal is.

(tools voor Tabaksfabrieken, been there, done that, forgot all about it).

[pedorus]

sinasappel schreef op maandag 23 november 2015 @ 09:38:
Dit kun je toch gewoon doen met een Excel solver? En als je je daar een beetje in verdiept kun je het zelfs automatiseren.

Dat kan inderdaad, maar kan ook makkelijk breken enzo, en het is de vraag hoe goed dat schaalt. Als het probleem klein genoeg is, en je Excel niet update, dan kan het goed gaan. Ik zou liever naar iets als GAMS, AIMMS, GLPK, enz. kijken.

P_Tingen schreef op maandag 23 november 2015 @ 09:31:
Maar we zijn vast niet de eersten die een probleem als dit moeten tackelen. Het probleem is alleen: hoe heet mijn probleem of hoe heet het algoritme dat ik zoek?

Linear Programming / Simplex? Het probleem is niet duidelijk genoeg geschetst voor een goede conclusie, zou kunnen dat het alsnog NP-compleet is bijvoorbeeld, dit ligt aan de voorwaarden.

En jullie zijn zeker niet de eersten, op hetzelfde industriegebied zitten minstens twee bedrijven die hier expert in zijn (TNO, Ortec), en in dezelfde stad schijnt ook een universiteit te zitten

[begintmeta]

Een heldere formele weergave van de voorwaarden maken is sowieso een goede start lijkt me.
Verder doet het me nogal denken aan een soort 'Diet Problem'. Daarover is erg veel te vinden in ieder geval, ook gespecialiseerde tools.

[P_Tingen]

pedorus schreef op dinsdag 24 november 2015 @ 00:02:
[...]
Dat kan inderdaad, maar kan ook makkelijk breken enzo, en het is de vraag hoe goed dat schaalt. Als het probleem klein genoeg is, en je Excel niet update, dan kan het goed gaan. Ik zou liever naar iets als GAMS, AIMMS, GLPK, enz. kijken.

Linear Programming / Simplex? Het probleem is niet duidelijk genoeg geschetst voor een goede conclusie, zou kunnen dat het alsnog NP-compleet is bijvoorbeeld, dit ligt aan de voorwaarden.

En jullie zijn zeker niet de eersten, op hetzelfde industriegebied zitten minstens twee bedrijven die hier expert in zijn (TNO, Ortec), en in dezelfde stad schijnt ook een universiteit te zitten

De schaal-, breekbaar- en robuustheid van Excel zit mij ook niet helemaal lekker. Bovendien moeten we dan een windows server hier zoeken. Hebben we wel, maar de beheerders zijn weer niet happig om daar office op te installeren. Neemt niet weg dat de solver wel een mooi ding is! Ik kende die nog niet. Mijn probleem is volgens mij inderdaad een LP probleem. Daar kunnen we verder mee zoeken. Thx voor de links.

We gaan vandaag met een paar knappen koppen bij elkaar zitten om een list te verzinnen.

En wat locatie betreft zit je zo'n 50 km mis. Geen universiteit hier. Wel skûtsjes.

[wimjongil]

P_Tingen schreef op dinsdag 24 november 2015 @ 09:35:
[...]

De schaal-, breekbaar- en robuustheid van Excel zit mij ook niet helemaal lekker. Bovendien moeten we dan een windows server hier zoeken. Hebben we wel, maar de beheerders zijn weer niet happig om daar office op te installeren. Neemt niet weg dat de solver wel een mooi ding is! Ik kende die nog niet. Mijn probleem is volgens mij inderdaad een LP probleem. Daar kunnen we verder mee zoeken. Thx voor de links.

We gaan vandaag met een paar knappen koppen bij elkaar zitten om een list te verzinnen.

En wat locatie betreft zit je zo'n 50 km mis. Geen universiteit hier. Wel skûtsjes.

Die solver gebruikt gewoon de simplex methode (dat is inderdaad linear programmeren), dat kun je ook in andere talen wel gebruiken. R is gratis en kan dit gewoon.

Aan de RUG zijn vast wel een paar Friese econometriestudenten die dit voor je kunnen doen. Ken er zelf ook wel een paar.

Als je eenmaal al je constraints op een rijtje hebt, is het probleem al een stuk simpeler. Ik zou daar dan ook mee beginnen: beschrijf wat je wilt maximaliseren/minimaliseren, aan welke voorwaarden elke blend moet voldoen en hoeveel je van elke tabaksoort hebt. Als je dit op een rijtje hebt zie je al weer veel beter wat de kern van het probleem is.

[P_Tingen]

wimjongil schreef op dinsdag 24 november 2015 @ 14:58:
[...]
Als je eenmaal al je constraints op een rijtje hebt, is het probleem al een stuk simpeler. Ik zou daar dan ook mee beginnen: beschrijf wat je wilt maximaliseren/minimaliseren, aan welke voorwaarden elke blend moet voldoen en hoeveel je van elke tabaksoort hebt. Als je dit op een rijtje hebt zie je al weer veel beter wat de kern van het probleem is.

Klopt, daar zijn we inmiddels ook achter

We hebben vanmiddag een vruchtbare sessie gehad; we hebben de solver ingericht voor een relatief kleine werkorder. Dit maakt wel heel erg inzichtelijk wat onze regels zijn; we laten de solver doorrekenen en die komt met een oplossing. Vervolgens kijken we of dat hout snijdt en welke regels we moeten toevoegen of veranderen. We gaan de solver niet gebruiken want teveel twijfel aan schaalbaarheid etc, maar het is wel een hele handige tool om het probleem inzichtelijk te maken.