Hoe bewijs ik dat mijn probleem NP-lastig is?

[Oscar Mopperkont]

Inleiding:
Ik ben voor mijn afstuderen bezig met het toewijzen van artikelen aan locaties in een magazijn.
Het magazijn heeft een aorta, transportband die een rondje maakt, met een x aantal uitsluispunten. Een orderdrager, waarin een order verzameld moet worden, gaat rond op de aorta en wordt uitgesluisd naar een pick-to-light zone als het artikelen nodig heeft uit die zone.
Elke order bestaat uit meerdere orderregels. In 1 orderregel staat hoeveel stuks van welk artikel verzameld moeten worden.
Elke orderregel leidt tot 1 pick van een artikel.

Optimaliseringsprobleem
Nu wil ik over een x aantal zones de artikel zodanig verdelen dat:
1) De werklast in elke zone gelijk is, dus aantal picks per zone gelijk
2) Een order zo min mogelijk zones aan doet. Dit kun je bereiken door artikelen die vaak bij elkaar in een order voorkomen ook bij elkaar in de zone te leggen (Dit is overigens een benadering, maar wel een goede). Ik noem dit even combinaties.


<sub>Dit is voor sommigen misschien makkelijk om het wat inzichtelijker te maken

Het eerste criterium komt overeen met het parallelle machine probleem, met een vast aantal jobs (lees artikelen) per machine(lees zone).
Het aantal picks in een zone komt dan overeen met de makespan bij het probleem. De makspan is de tijd die het in totaal kost voordat de laatste machine klaar is.

Het tweede probleem is vergelijkbaar met het "Uniform Graph Partitioning" probleem, waarbij chips dusdanig over twee printplaten (lees zones) verdeeld moeten worden zodat het aantal verbindingen (lees combinaties) tussen de printplaten onderling minimaal is, en het aantal verbindingen op de printplaat dus maximaal is.
Elke chip heeft 0 of meer verbinidngen met ander chips.</sub>


ILP formulering
Plaatje ziet er zo een beetje verrot uit... Maar hij staat gelinkt naar het origineel dat wel goed leesbaar is.



Wat wil ik nu?
Ik wil aantonen (bewijzen kun je niet zeggen) dat dit probleem, zeer waarschijnlijk NP-lastig is. Daarvoor moet je eerst de stappen doen met NP-compleet bewijzen enzo, en dat het in de klasse NP zit.
Ik heb daar wel wat literatuur over, maar ik heb nergens voorbeelden van hoe je het nu echt daadwerkelijk "bewijst".


_{Optimaliseringsproblemen behoren niet tot de klasse NP, maar heten NP-lastig indien hun beslissingsvariant NP-compleet is.}

[ Voor 73% gewijzigd door Oscar Mopperkont op 01-07-2003 11:45 . Reden: Mensen vonden omschrijving niet goed. ]

[joepP]

Als je het probleem net zo vaag in je hoofd hebt zitten als je het hier neerkalkt verbaast het me niets dat je het niet kan bewijzen. Probeer het probleem nou eens fatsoenlijk uit te leggen, met een voorbeeldje bijvoorbeeld...

[heintjeput]

Gelukkig snap jij het ook al niet, want ik snap er geen hol van en ik dacht dat het aan mij lag, wat dus niet zo is.

[Lord Daemon]

Inderdaad, als je het probleem in wiskundig duidelijke termen hier neer kan zetten - dus zonder ervan uit te gaan dat wij weten wat termen als 'picks' en 'makespan' betekenen - zijn zowel wij als jij waarschijnlijk een stap verder.

Bewijzen dat iets NP-complex is, is trouwens niet zo lastig. Je hoeft alleen te laten zien dat er een polynomiaal algoritme bestaat waarmee je een gegokte (of gegeven) oplossing kan checken op correctheid. Of bedoel je wellicht dat je moet laten zien dat het probleem NP-compleet is? (Waarmee je dan niet hebt bewezen, maar wel enigszins aannemelijk hebt gemaakt, dat het probleem niet P-complex is. Let wel, een probleem kan best NP-complex en P-complex tegelijk zijn; P-complexiteit impliceert namelijk NP-complexiteit.)

Extra uitleg voor wie deze termen niet kent:
* Een probleem is P-complex als er een polynomiaal algoritme bestaat dat oplossing vindt; dwz, een algoritme waarvan de duur om het uit te voeren met het aantal elementen in het probleem (hier dus aantal zones, locaties en artikelen) toeneemt volgens een polynomiale functie. (Niet volgens een exponentiele functie dus, bijvoorbeeld.)
* Een probleem is NP-complex als er een polynomiaal algoritme bestaat dat een gegeven oplossing kan checken; dwz, als iemand je een 'oplossing' geeft, kan je in polynomiale tijd bekijken of die oplossing klopt. Dit is in ieder geval op het eerste gezicht een minder strenge eis dan P-complexheid.
* Een probleem is NP-compleet wanneer geldt dat a) het probleem NP-complex is, en b) indien er een polynomiaal algoritme gevonden wordt om het op te lossen, dus het probleem P-complex blijkt te zijn, dat dan automatisch volgt dat alle NP-complexe problemen ook P-complex zijn.
* De equivalentie of non-equivalentie van P-complexiteit en NP-complexiteit is een open vraagstuk. Men vermoedt dat NP-complete problemen niet P-complex zijn, dat er dus geen polynomiale oplossingsalgoritmen voor bestaan, maar dit is niet zeker. Wie een NP-compleet probleem binnen polynomiale tijd weet op te lossen wordt - zo voorspel ik - de beroemdste wiskundige van de 21e eeuw.

[Oscar Mopperkont]

Sorry d8 dat termen als picks en makespan, wel bekende termen zijn. Heb nu even geen tijd, maar ga morgen een langere, en hopelijk duidelijkere, uitleg geven. Met voorbeelden, en wiskundig duidelijke termen.

[joepP]

Lord Daemon schreef op 30 June 2003 @ 17:57:
Bewijzen dat iets NP-complex is, is trouwens niet zo lastig. Je hoeft alleen te laten zien dat er een polynomiaal algoritme bestaat waarmee je een gegokte (of gegeven) oplossing kan checken op correctheid. Of bedoel je wellicht dat je moet laten zien dat het probleem NP-compleet is? (Waarmee je dan niet hebt bewezen, maar wel enigszins aannemelijk hebt gemaakt, dat het probleem niet P-complex is. Let wel, een probleem kan best NP-complex en P-complex tegelijk zijn; P-complexiteit impliceert namelijk NP-complexiteit.)

Klok? Klepel?

Jij geeft de definitie voor het NP-oplosbaar zijn voor een probleem, wat hetzelfde is als zeggen dat het probleem in NP zit. Bewijzen dat dat zo is is (meestal) triviaal.

NP-hard (=NP-moeilijk = NP-complex) betekent dat ELK probleem in NP tot dit probleem reduceert. Dit kan je bewijzen door een willekeurig NP-compleet (zie verderop) probleem te reduceren tot jouw probleem.

NP-compleet betekent dat het probleem -en- NP-hard -en- in NP zit.

[mcb1]

Maak even duidelijk wat je nu bedoelt.

Heb het idee dat je een logistiek probleem met een productiebeheersings-probleem aan het mengen bent.

in eerste instantie heb ik het idee dat je een magazijn hebt met daarin stellingen. Vanuit deze stellingen wil je de producten zo snel mogelijk uit het magazijn naar een machine vervoeren.

Als tweede denk ik dat je te maken hebt met machines en dat je de levertijdsoverschrijding moet berekenen. (Makespan)

Omschrijf nauwkeurig wat je wilt en maak een tekening van de situatie met daarin de relevante waarden.

[Oscar Mopperkont]

mcb1 schreef op 01 juli 2003 @ 10:41:
Maak even duidelijk wat je nu bedoelt.

Heb het idee dat je een logistiek probleem met een productiebeheersings-probleem aan het mengen bent.

in eerste instantie heb ik het idee dat je een magazijn hebt met daarin stellingen. Vanuit deze stellingen wil je de producten zo snel mogelijk uit het magazijn naar een machine vervoeren.

Als tweede denk ik dat je te maken hebt met machines en dat je de levertijdsoverschrijding moet berekenen. (Makespan)

Omschrijf nauwkeurig wat je wilt en maak een tekening van de situatie met daarin de relevante waarden.

Je zit heel erg dicht in de buurt ja! Het komt er binnen een paar uur aan! Het staat er nu hopelijk duidelijker

[ Voor 4% gewijzigd door Oscar Mopperkont op 01-07-2003 11:43 ]

[mcb1]

Technische bedrijfskunde! Dacht al dat je daar iets mee te maken had........ effe in je Profile gekeken en het blijkt nog waar te zijn ook.

Kom maar op met je probleem, hier nog een technisch bedrijfskundige!
(Als ik al dicht in de buurt zit dan heb ik al een idee waar je naartoe wilt met je probleem)

Let wel dat je zo weinig mogelijk "vaktaal" gebruikt in je omschrijving. Ik snap het wel, maar die wiskunde-student die jou wel een handje wilt helpen niet!

[Oscar Mopperkont]

mcb1 schreef op 01 July 2003 @ 11:45:
Technische bedrijfskunde! Dacht al dat je daar iets mee te maken had........ effe in je Profile gekeken en het blijkt nog waar te zijn ook.

Kom maar op met je probleem, hier nog een technisch bedrijfskundige!
(Als ik al dicht in de buurt zit dan heb ik al een idee waar je naartoe wilt met je probleem)

Let wel dat je zo weinig mogelijk "vaktaal" gebruikt in je omschrijving. Ik snap het wel, maar die wiskunde-student die jou wel een handje wilt helpen niet!

offtopic:
Idd Duidelijk TBK probleem, met voor TBK-ers misschien wat veel wiskunde , daarom vraag ik het maar hier, want de wiskundgen schudden zo'n bewijs gewoon uit de mouw!

Is het nu denk je duidelijk? Want ik kijk er toch altijd door een TBK bril doorheen, en dat lijkt alles duidelijk voor iedereen, maar dan is het soms toch wartaal, zoals in mij originele opening

Het "probleem" optimaliseer ik overigens nu met Simulated Annealing, en dat werkt heel erg goed, maar moet dus wel aantonen dat het gerechtvaardigd is dat ik een heuristiek gebruik

[ Voor 10% gewijzigd door Oscar Mopperkont op 01-07-2003 11:50 ]

[mcb1]

Waarom wil je bewijzen dat dit probleem lastig is?

- Heb je al een oplossing bedacht en heb je moeite om deze te verdedigen?
- Begin je er net aan en denk je op deze manier het probleem op te lossen?
- Wil je bewijzen dat dit probleem niet op te lossen is?

[Oscar Mopperkont]

mcb1 schreef op 01 July 2003 @ 11:57:
Waarom wil je bewijzen dat dit probleem lastig is?

- Heb je al een oplossing bedacht en heb je moeite om deze te verdedigen?
- Begin je er net aan en denk je op deze manier het probleem op te lossen?
- Wil je bewijzen dat dit probleem niet op te lossen is?

Laatste ik wil bewijzen dat het probleem NP-Lastig is en het dus gerechtvaardidg is dat ik een heuristiek (in mijn geval Simulated Annealing) gebruik om het probleem op te lossen.

Iedereen voelt wel op zijn klompen aan dat het een moeilijk probleem is, maar ik wil, daar het voor mijn afstuderen is, zoveel mogelijk onderbouwen.

[mcb1]

oke, je gebruikt dus een simulatie programma!

Heb ook met een simulatie programma gewerkt genaamd "Taylor"

In dit programma heb ik ook wel een een simulatie gemaakt van een soortgelijk probleem. Nu snap ik dat je wilt bewijzen dat het door jouw gekozen programma de beste oplossing is.

Jouw probleem is moeilijk op te lossen, volgens mij mis je nog aardig wat variabelen. (abc-artikelen, onzekerheid in de vraag, grilligheid in aankomstproces enz.)

Nu neem ik aan dat je aan het einde van je afstuderen bent gkomen en dat de tijd erg beperkt is?
Ik zou hier dan niet meer aan beginnen, ik denk ook niet dat je hier vragen over zult krijgen. (Je kunt beter bekijken of je alle variabelen in je model wel goed hebt ingevoerd en onderbouwen waarom je dit gedaan hebt)

[Oscar Mopperkont]

mcb1 schreef op 01 July 2003 @ 12:17:
oke, je gebruikt dus een simulatie programma!

offtopic:
Ja ik gebruik een simulatieprogramma, eM-Plant, maar hoe kun jij dat opmaken uit mijn posts Ik gebruik het om te bepalen hoe hoog de output van het magazijn gaat worden, EN om te verifieren of een indeling gemaakt door mij, ook goed is. Verder kan ik verschillende indelingen proberen, waarbij OF gelijke belasting belangrijker is OF waarbij meer nadruk op combinaties gelegd wordt.

Heb ook met een simulatie programma gewerkt genaamd "Taylor"

offtopic:
Nope, op de UT gebruiken we Simple++/eM-Plant
Waar studeer jij eigenlijk, aan de TUe?

In dit programma heb ik ook wel een een simulatie gemaakt van een soortgelijk probleem. Nu snap ik dat je wilt bewijzen dat het door jouw gekozen programma de beste oplossing is.

offtopic:
Hmm, ik wil meer bewijzen dat ik Simulated Annealing mag gebruiken, een zoekalgoritme dat begint als random search en eindigt als local search. Waarbij er dus initieel ontsnapt kan wordne uit lokale optima.

Jouw probleem is moeilijk op te lossen, volgens mij mis je nog aardig wat variabelen. (abc-artikelen, onzekerheid in de vraag, grilligheid in aankomstproces enz.)

offtopic:
Ik mis eigenlijk helemaal geen variabelen Onzekerheid in vraag kan ik weinig over zeggen, omdat er niet zoveel historische gegevens zijn. ABC artikelen hangt af van vraag, die heb ik dus al wel voor 1 jaar.
Grilligheid aankomstproces doet niet echt ter zaken. Ik gebruik originele orderbestand van voorgaande jaar.

Nu neem ik aan dat je aan het einde van je afstuderen bent gkomen en dat de tijd erg beperkt is?
Ik zou hier dan niet meer aan beginnen, ik denk ook niet dat je hier vragen over zult krijgen. (Je kunt beter bekijken of je alle variabelen in je model wel goed hebt ingevoerd en onderbouwen waarom je dit gedaan hebt)

offtopic:
Ik heb nog twee maanden bij het bedrijf, en daarna nog even tijd om bi verslag puntjes op de i te zetten. Maar ik kan nu even niet verder, moet input van data hebben die even op zich laat wachten. Dus ga ik me alvast hiermee bezig houden.

Het gaat overigens wel allemaal heel erg offtopic nu....

[ Voor 12% gewijzigd door Oscar Mopperkont op 01-07-2003 12:30 ]

[mcb1]

Via google kwam ik erachter dat "Simulated Annealing" verdacht veel gebruikt wordt in een simulatie progje. vandaar.

Ik ben vorige week afgestudeerd aan de hogeschool 's-Hertogenbosch (ja, ja, geen TU)

------------------------------------------------------------------------------
Ik mis eigenlijk helemaal geen varaibalen Onzekerheid in vraag kan ik weinig over zeggen, omdat er niet zoveel historische gegevens zijn. ABC artikelen hangt af van vraag, die heb ik dus al wel voor 1 jaar.
Grilligheid aankomstproces doet niet echt ter zaken. Ik gebruik originele orderbestand van voorgaande jaar.
------------------------------------------------------------------------------

Ik weet natuurlijk niet precies wat je opdracht nu inhoud, maar de bovenstaande opmerking zou ik toch maar eens goed bekijken voordat je moet verdedigen. Ik heb een docent gehad die hier in tentamens e.d. vragen over gesteld heeft naar aanleiding van mijn model (Ging over SBA's i.c.m seizoensinvloeden e.d.)!

<EDIT>

Ik snap trouwens wel wat het probleem is, maar ik kan je er geen wiskundig onderbouwde oplossing voor geven.

[ Voor 15% gewijzigd door mcb1 op 01-07-2003 13:04 ]

[Lord Daemon]

joepP schreef op 30 June 2003 @ 19:25:
Klok? Klepel?

Nee, meer een slecht geheugen. Je hebt helemaal gelijk.

[Oscar Mopperkont]

mcb1 schreef op 01 July 2003 @ 13:00:
Ik weet natuurlijk niet precies wat je opdracht nu inhoud, maar de bovenstaande opmerking zou ik toch maar eens goed bekijken voordat je moet verdedigen. Ik heb een docent gehad die hier in tentamens e.d. vragen over gesteld heeft naar aanleiding van mijn model (Ging over SBA's i.c.m seizoensinvloeden e.d.)!

Ik zal er rekening mee houden

[Oscar Mopperkont]

Lord Daemon schreef op 01 July 2003 @ 13:05:
[...]
Nee, meer een slecht geheugen. Je hebt helemaal gelijk.

Ik neem aan dat jij geen TBK-er bent? Heb ik het probleem nu wel duidelijk omschreven, of moet er nog wat meer aanvulling bij op bepaalde punten?

[joepP]

Oscar Mopperkont schreef op 30 June 2003 @ 15:43:
Wat wil ik nu?
Ik wil aantonen (bewijzen kun je niet zeggen) dat dit probleem, zeer waarschijnlijk NP-lastig is. Daarvoor moet je eerst de stappen doen met NP-compleet bewijzen enzo, en dat het in de klasse NP zit.
Ik heb daar wel wat literatuur over, maar ik heb nergens voorbeelden van hoe je het nu echt daadwerkelijk "bewijst".

Nee.

Als je wilt bewijzen dat een probleem NP-hard is, hoef je alleen een reductie van een bekend NP-compleet probleem naar je eigen probleem te geven. Als je dan ook nog kan aantonen dat je probleem in NP zit (triviaal in dit geval), heb je bewezen dat je probleem NP-compleet is.

[joepP]

Je bewijst reductie van graph-bipartitioning (GB) het makkelijkst. Dit is het vinden van een verdeling van een ongerichte graaf in 2 even grote groepen, zodanig dat het aantal verbindingen TUSSEN de 2 delen minimaal is. Dit is een bekend NP-compleet probleem.

Je maakt 2 zones.
De knopen zijn je producten.
Elke verbinding tussen (u, v) wordt een order (u, v).
De capaciteit van de zone wordt precies de helft van het aantal knopen in de graaf.

Als jouw algoritme perfect zal werken, vindt het precies die verdeling, die de beste oplossing is voor het GB-probleem is. GB is NP-compleet, dus jouw probleem is NP-hard. Omdat je probleem ook nog in NP zit, is het zelfs NP-compleet.

[Oscar Mopperkont]

joepP schreef op 01 July 2003 @ 16:44:
Je bewijst reductie van graph-bipartitioning (GB) het makkelijkst. Dit is het vinden van een verdeling van een ongerichte graaf in 2 even grote groepen, zodanig dat het aantal verbindingen TUSSEN de 2 delen minimaal is. Dit is een bekend NP-compleet probleem.

Je maakt 2 zones.
De knopen zijn je producten.
Elke verbinding tussen (u, v) wordt een order (u, v).
De capaciteit van de zone wordt precies de helft van het aantal knopen in de graaf.

Als jouw algoritme perfect zal werken, vindt het precies die verdeling, die de beste oplossing is voor het GB-probleem is. GB is NP-compleet, dus jouw probleem is NP-hard. Omdat je probleem ook nog in NP zit, is het zelfs NP-compleet.

Ik volg je totaal niet om eerlijk te zijn.

[joepP]

Oscar Mopperkont schreef op 01 juli 2003 @ 21:17:
[...]

Ik volg je totaal niet om eerlijk te zijn.

Wat ik doe, is het een willekeurige instantie van het graph-bipartionings probleem op jouw eigen probleem afbeelden. Zodoende laat ik dus zien dat jouw probleem minstens net zo moeilijk is, en dus NP-hard.

offtopic:
NOFI, maar als je de rest niet kan volgen vraag ik me serieus af waarom je op dit onderwerp af gaat studeren...

[Oscar Mopperkont]

joepP schreef op 01 July 2003 @ 21:44:
[...]


Wat ik doe, is het een willekeurige instantie van het graph-bipartionings probleem op jouw eigen probleem afbeelden. Zodoende laat ik dus zien dat jouw probleem minstens net zo moeilijk is, en dus NP-hard.

offtopic:
NOFI, maar als je de rest niet kan volgen vraag ik me serieus af waarom je op dit onderwerp af gaat studeren...

offtopic:
Ik studeer niet af op het bewijzen of iets NP-lastig is, het is ook niet strikt noodzakelijk dat ik he bewijs. Maar het is wel netter als ik het bewijs. De "beoordelaars" weten ook wel dat ik geen wiskundige ben ofzo.

[Oscar Mopperkont]

Daar het probleem een combinatie is van een variant op het UGP en parallelle machine probleem, mag ik dan zeggen dat als ik ergens vind dat iemand bewezen heeft dat het UGP probleem en het Parallell machine probleem NP-lastig is, dat het gecombineerde probleem ook NP-lastig is? (Ondanks de extra restricties?)

[joepP]

Oscar Mopperkont schreef op 03 July 2003 @ 10:54:
Daar het probleem een combinatie is van een variant op het UGP en parallelle machine probleem, mag ik dan zeggen dat als ik ergens vind dat iemand bewezen heeft dat het UGP probleem en het Parallell machine probleem NP-lastig is, dat het gecombineerde probleem ook NP-lastig is? (Ondanks de extra restricties?)

Als jij een bekend probleem kan afbeelden op jouw probleem, zoals ik hierboven met GB deed, is dat genoeg. Vraag je dus af: als ik jou een UGP (of Parallel Machine probleem) geef, kan je dat dan oplossen met een oplosser voor jouw probleem? Zo ja, dan is het NP-lastig, zo nee dan kan je een ander probleem nemen als uitgangspunt.

[Verwijderd]

Ik ben nu met een soortgelijke afstudeeropdracht bezig. Ik moet voor de logistieke/magazijn-afdeling van een bedrijf in elektrotechnische onderdelen voorstellen doen om de efficientie van het orderpicken te verbeteren. Uiteraard moet ik deze voorstellen ook goed onderbouwen.

Aangezien jij al een tijdje bezig / klaar bent met je opdracht kan je mij misschien wat tips geven op dit gebied.

Alvast bedankt

[Oscar Mopperkont]

Dat hangt er helemaal vanaf hoe ze daar werken. Als je het in het algemeen hebt over order picken in een magazijn dan kun je het beste een boek/reader over warehousing erbij pakken. Ik weet niet waar je studeert, maar mocht je toevallig TBK-er zijn aan de UT en je hebt het vak warehousing niet gehad dan zou ik ff naar de bieb gaan en die reader erbij pakken. Daar staat echt een heleboel nuttige informatie in

[jeanj]

[quote]Oscar Mopperkont schreef op dinsdag 01 juli 2003 @ 12:24:

offtopic:
Hmm, ik wil meer bewijzen dat ik Simulated Annealing mag gebruiken, een zoekalgoritme dat begint als random search en eindigt als local search. Waarbij er dus initieel ontsnapt kan wordne uit lokale optima.

Ik begrijp de link tussen het bewijzen dat een probleem NP-lastig (off topic WTF, ik haat dat men wordt geleerd een Nederlandse vertaling te gebruiken, gebruik toch de engelse term) en het gebruik van Simulated Annealing niet, ik ben niet zo up ta date met het gebruik van SA. De vraag of Simulated Annealing kan werken is toch afhankelijk van je objective function (NL doel, of doelstellings functie?) en de tuning van je SA algorithme (stap grootte).

offtopic: wat is de NL vertaling van Simulated Annealing
oftopic 2: leuk dat SA zo veel gebruikt wordt, toen ik het 10 jaar geleden gebruikt voor mijn afstuderen was het nog even zoeken naar uitleg .....

[Oscar Mopperkont]

[quote]jeanj schreef op woensdag 14 september 2005 @ 21:33:

Oscar Mopperkont schreef op dinsdag 01 juli 2003 @ 12:24:
Ik begrijp de link tussen het bewijzen dat een probleem NP-lastig (off topic WTF, ik haat dat men wordt geleerd een Nederlandse vertaling te gebruiken, gebruik toch de engelse term) en het gebruik van Simulated Annealing niet,

Ik doelde daar op rechtvaardigen. Als het probleem niet NP lastig is dan zou ik eventueel ook kunnen zoeken naar een methode die het wel exact oplost. Maar goed ikben inmiddels met een 8 afgestudeerd, dus het is ook niet echt relevant meer.