Efficient pakketten kiezen

[Jorim]

Situatie: Je werkt op een laboratorium en op het lab worden verscheidene testen uitgevoerd. Sommige van deze testen kunnen gegroepeerd uitgevoerd worden en vanuit efficiency heeft dit ook de voorkeur. De 'klant' zal altijd losse testen aanvragen en het is aan het lab om de meest efficiënte groep(en) en losse testen te kiezen.
 
Voorbeeld:
Mogelijke testen: A, B, C, D, E
Testpakketten: 1 (A, C), 2 (A, B, C)
 
Als de klant vraagt om AC dan gaan we voor pakket 1, als de klant vraagt om ABC dan gaan we voor pakket 2, als de klant vraagt om ACE dan pakket 1 + test E, etc.
 
Uitgaande van een paar regels zoals:

• Testen worden maar 1 keer aangevraagd
• Volgorde is niet relevant
• Alleen volledige pakketten worden gedaan
• Pakketten kunnen overlap vertonen

zijn er een redelijk beperkt aantal aanvragen mogelijk en dus ook een vrij beperkt aantal oplossingen:

• A; test A
• AB; test AB
• AC; pakket 1
• AD; test AD
• AE; test AE
• ABC; pakket 2
• ABD; test ABD
• ABE; test ABE
• ACD; pakket 1, test D
• ACE; pakket 1, test E
• ADE; test ADE
• BCD; test BCD
• BCE; test BCE
• BDE; test BDE
• ABCD; pakket 2, test D
• ABCE; pakket 2, test E
• ABDE; test ABDE
• ACDE; pakket 1, test DE
• BCDE; test BCDE
• ABCDE; pakket 2, test DE

Stel ik heb een honderdtal testen en een tiental pakketten dan is uitschrijven geen optie meer. Menselijk inzicht werk behoorlijk goed, maar ik wil het graag berekenen / programmeren. Wat is wiskundig gezien de beste aanpak?
 
En gelijk een vervolgvraag. Stel de regel van 'volledige pakketten' komt te vervallen en ik hang een prijs aan de testen en aan de pakketten (waarbij het dus goedkoper kan zijn om een heel pakket te doen, terwijl er dan wellicht een niet aangevraagde test wordt uitgevoerd) en ik wil de goedkoopste samenstelling. Hoe pak ik het dan aan?
 
Een beetje veel tekst, maar in minder woorden kan ik het niet uitleggen. Bedankt voor het meedenken!

[Emveedee]

Hoeveel testen worden er tegelijkertijd aangevraagd? Bij honderd testen heb je al ordegrootte 10^30 mogelijke combinaties van verschillende testen, dus voor deze allemaal de goedkoopste optie berekenen is geen optie. Echter, stel dat er 10 testen tegelijk aangevraagd worden, dan is het aantal combinaties nog te overzien. Je kunt dan best simpelweg door alle opties heengaan en de goedkoopste kiezen.

 

Bovendien kun je er vanuit gaan dat een pakket altijd goedkoper is dan de losse testen samen (anders is het nooit voordelig om voor het pakket te kiezen). Je kunt dan ook een hoop opties wegstrepen.

 

Als je een efficiëntere methode wil zou ik een recursief proces gebruiken, zoiets als dit:

• Ga met een loopje door alle (relevante) pakketten heen, van groot naar klein (input bijv. A,B,C,D,E)
  • Kijk welke testen er overblijven (bijv. D,E)
  • begin weer opnieuw met eenzelfde loop (zelfde functie, maar met minder parameters dus)
  • De nieuwe loop mag kiezen uit pakketten die maximaal even groot zijn als het eerste pakket

Het idee is dat je als een soort van boomstructuur door alle mogelijke opties gaat, en tegelijkertijd kun je natuurlijk de kosten uitrekenen.
 
Het kan nog steeds wel voorkomen dat bepaalde opties dubbel in je lijst komen (bijv. eerst pakket ABC, daarna DEF,  en later nog eens DEF + ABC). Je zou daar evt nog iets in je loop voor kunnen inbouwen, maar waarschijnlijk is het makkelijker om de dubbele er achteraf uit te filteren. Je voorkomt al een hoop dubbele doordat je van groot naar klein gaat.
 
 
Edit:
Ik bedenk me net dat als een pakket in de 'hoofdloop' aan de beurt is geweest, dan zijn alle mogelijke opties met dat pakket al uitgerekend. Je kunt dat pakket dan dus uitsluiten voor de rest.

[PAAC]

Voor alle gevallen is het lastig na te rekenen, maar een mogelijkheid is dan misschien een heuristische oplossing van het handelsreiziger probleem? Hierbij is dan een node een pakket(of losse bepaling), en de afstand tussen twee nodes de extra kosten die er per pakket bij komen.

Wanneer je dan een selectie maakt van de benodigde nodes, hoef je daarna alleen maar de "kortste route" (ofwel goedkoopste route)  te bepalen.

[PAAC]

Hier nog een video met het achterliggende idee van wat ik bedoel:

[Jorim]

Bedankt voor jullie antwoorden heren!
 
Ik ben het volledig eens met jouw logica Emveedee en ik denk dat die logica een efficiënte versie is van wat Paac voorstelt, maar zonder alle mogelijkheden te berekenen. Maar naar mijn idee 'bereken' je nog lang niet de meest efficiënte methode (wat wellicht ook gewoon niet kan)..
 
Stel in mijn voorbeeld met mogelijke testen: A, B, C, D, E
Heb ik nu testpakketten: 1. (A, B, C), 2. (A, B), 3. (C, D) (kosten losse testen 100 euro, 2-combi 180, 3-combi 270)
En ik wil test ABCD gedaan hebben...
 
Als ik nu mijn pakketten sorteer op gemiddelde prijs per test (laag-hoog) en grootte (groot-klein) dan krijg ik volgorde: 1, 2/3
 
Dit betekend dus dat ik voor pakket 1 met losse test D ga en dat kost me 270+100=370 euro
terwijl pakket 2 en 3 samen minder kost, namelijk 180+180=360
 
Nu belazer ik de zaak een beetje door de 3-combi gemiddeld niet goedkoper te maken dan de 2-combi, maar dat kan afhankelijk van uitvoer / aanvraag / complexiteit een logische keuze zijn..
 
Zou ik dit verhelpen door 'meer' beginpakketten door te rekenen? In dit geval zou ik de zaak kunnen doorrekenen voor alle eerst gekozen pakketten met dezelfde laagste gemiddelde prijs. Iets meer werk, maar nog steeds niet alle opties als de hoeveelheden groter worden.

[Emveedee]

Waarom zou je stoppen na de eerste optie? Tenzij je echt heel veel testen en pakketten hebt is het aantal combinaties nog wel te overzien. Ik zou in dat geval gewoon alle opties berekenen. Bovendien is het aannemelijk dat combinaties met grotere pakketten goedkoper zullen zijn. Als het er echt teveel zijn zou je dus bijv. kunnen stoppen na, noem eens iets, 100k combinaties.
 
Je zou ook afhankelijk van de totaalprijs de loop af kunnen breken. Als bijv. in de laatste 1000 combinaties niet meer de goedkoopste optie is geweest, gaan ze waarschijnlijk alleen nog maar duurder worden.
 
Overigens zie ik niet waarom je niet gewoon voor een brute force aanpak zou gaan, 500k combinaties doorrekenen moet best te doen zijn in een halve minuut ofzo.

[Jorim]

Waarom zou je stoppen na de eerste optie?

...

Overigens zie ik niet waarom je niet gewoon voor een brute force aanpak zou gaan, 500k combinaties doorrekenen moet best te doen zijn in een halve minuut ofzo.

Ik probeer een beetje een balans te vinden tussen capaciteit / tijd en wat 't oplevert. Maar hoogstwaarschijnlijk heb je wel gelijk dat alles doorrekenen meestal prima kan..

 

Je zou ook afhankelijk van de totaalprijs de loop af kunnen breken. Als bijv. in de laatste 1000 combinaties niet meer de goedkoopste optie is geweest, gaan ze waarschijnlijk alleen nog maar duurder worden.

Dat vind ik wel een mooie optie