Springen naar inhoud

Bin-packing


  • Log in om te kunnen reageren

#1

A.Square

    A.Square


  • >250 berichten
  • 251 berichten
  • Ervaren gebruiker

Geplaatst op 11 september 2007 - 09:49

Ik heb, samen met een medestudent, opdracht gekregen een bin packing probleem te onderzoeken.

Echter hebben wij slechts vier bins beschikbaar (met ieder een gelijke capaciteit van 1). Wanneer er een inpakopdracht wordt gegeven die zeker niet past moet dat gerapporteerd worden. Wanneer er zeker een mogelijkheid is om alle items in te pakken moet dat gebeuren.
Het maakt echter absoluut niet uit hoe de items in de bins zitten (het is bijvoorbeeld geaccepteerd vier items met een gewicht van slechts 0.1 te gelijk te verdelen over de vier bins)

Dit bin packing probleem verschilt van die in de literatuur in het feit dat het aantal bins en het aantal items eindig is.

Ons aanvankelijke probleem is het analyseren van de gegevens, wij zien niet direct een sluitende methode om uit te zoeken of de items wel daadwerkelijk in de bins gaan passen.
Wij hebben nu de twee schamele eisen dat het de som van de gewichten de items niet groter mag zijn dan 4 en dat er niet meer dan 4 items mogen zijn met capaciteit groter dan 0.5
Weet iemand een methode om hier systematisch over te kunnen zeggen?

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 11 september 2007 - 10:05

Mag je brute force te werk gaan? Bij n items zijn er 4n mogelijkheden (ruim genomen, een aantal valt voortijdig af of zijn dubbel), is dat te doen bij de orde van grootte van n die hier gebruikt wordt?

Veranderd door Rogier, 11 september 2007 - 10:08

In theory, there's no difference between theory and practice. In practice, there is.

#3

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 11 september 2007 - 11:00

Ons aanvankelijke probleem is het analyseren van de gegevens, wij zien niet direct een sluitende methode om uit te zoeken of de items wel daadwerkelijk in de bins gaan passen.

Ik denk dat dit een gevalletje 'proberen' is. Maar wat zijn de regels die gelden voor of een item past of niet?

#4

A.Square

    A.Square


  • >250 berichten
  • 251 berichten
  • Ervaren gebruiker

Geplaatst op 11 september 2007 - 18:18

@Rogier: Brute force is natuurlijk een laatste redmiddel. Een algoritme met een complexiteit van O(4^n) wordt niet echt hoog beoordeeld. We gebruiken dat gegeven natuurlijk wel om enkele dingen af te schatten tegen een bovengrens.

@EvilBro: Een item past in een bin wanneer de resterende ruimte in de bin groter of gelijk is aan het gewicht van het item.

Een bezoekje aan de bieb vanmiddag leerde mij dat er ook zoiets is als een meervoudig knapzak-probleem (multiple knapsack). En die lijkt in aanpak wel wat op mijn probleem.

Nadere suggesties hoor ik graag. En van mijn kant bij deze de belofte jullie op de hoogte te houden van onze vorderingen.

#5

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 11 september 2007 - 18:54

Ik had zelf het idee om de items op gewicht te sorteren en dan zo te beginnen met opstapelen (nieuwe bin beginnen als item niet in een van de voorgaande past). Na wat te googlen blijkt dit de FFD (First Fit Decreasing) strategie te zijn. Het aantal bins dat je hiervoor nodig hebt is maximaal LaTeX . Je zou dus kunnen kijken hoeveel bins je zo nodig hebt. Als het er 4 of minder zijn dan heb je het probleem opgelost. Als het er 6 of meer zijn, kan het niet. Alleen zal je dan bij 5 bins nog verder onderzoek moeten doen.

Maar er zijn vast betere oplossing (een oplossing die mij meteen te binnen schiet kan nooit bijster efficient zijn pi.gif ). Zoeken in google op "bin packing algorithm" levert veel materiaal op. Dat gecombineerd met papieren internet (de bieb) levert geheid een efficient algoritme op.

Hopelijk heb je hier iets aan. Succes!

#6

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 11 september 2007 - 19:36

En beginnen met de eerste bin zo vol mogelijk te krijgen, en dan met de items die over zijn de tweede bin zo vol mogelijk, enz. Is dat wat?
In theory, there's no difference between theory and practice. In practice, there is.

#7

A.Square

    A.Square


  • >250 berichten
  • 251 berichten
  • Ervaren gebruiker

Geplaatst op 16 september 2007 - 16:24

Jij noemt het meest basale algoritme, Rogier.
Een voorbeeld van het nadeel hieraan is de volgende lijst van itemsgrootten: {0.6 ; 0.6 ; 0.3 ; 0.2 ; 0.2}
Jouw algoritme pakt als volgt in:
B1: 0.6
B2: 0.6 + 0.3
B3: 0.2 + 0.2

First Fit daarentegen kijkt steeds vanaf het begin naar de bins om te zoeken naar een plek die ruim genoeg is.
Die pakt het als volgt in:
B1: 0.6 + 0.3
B2: 0.6 + 0.2 + 0.2

Bedankt voor de grens EvilBro!

Wat betreft de voortgang:
We hebben geconstateerd dat er twee soorten algoritmes zijn: online en offline.
Online gaat er van uit dat de verzameling items onbekend is (dus pakt steeds een huidig item in met alleen de wetenschap wat de vorige items ware)
Offline gebruikt de volledige verzameling van items (dus heeft ook kennis over volgende items)
Op ons probleem is een Offline algoritme van toepassing.

#8

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 16 september 2007 - 22:45

Jij noemt het meest basale algoritme, Rogier.
Een voorbeeld van het nadeel hieraan is de volgende lijst van itemsgrootten: {0.6 ; 0.6 ; 0.3 ; 0.2 ; 0.2}
Jouw algoritme pakt als volgt in:
B1: 0.6
B2: 0.6 + 0.3
B3: 0.2 + 0.2

Dat is niet zo vol mogelijk. Op het moment dat een item niet in de huidige bin erbij past zou ik nog wel verder willen zoeken. Dan krijg je dus:
B1: 0.6 + 0.2 + 0.2
B2: 0.6 + 0.3

Sterker nog, met "de eerste bin zo vol mogelijk" bedoel ik de grootste van alle combinaties uit de items die in de eerste bin past. Dus niet per se alleen de lijst doorlopen in volgorde van grootte, al maakt dat in dit voorbeeld toevallig niet uit.
Als je bijvoorbeeld dit hebt: { 0.65 ; 0.6; 0.3 ; 0.2; 0.2; } zou ik krijgen:
B1: 0.6 + 0.2 + 0.2 (:!: want dat is voller dan 0.65 + 0.3)
B2: 0.65 + 0.3
In theory, there's no difference between theory and practice. In practice, there is.

#9

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 17 september 2007 - 07:52

Wat Rogier voorstelt heet (denk ik) het BFD algoritme (Best Fit Decreasing).

#10

Fred F.

    Fred F.


  • >1k berichten
  • 4168 berichten
  • Pluimdrager

Geplaatst op 20 september 2007 - 15:51

Het lijkt mij dat dit probleem op te lossen is met Integer Programming (IP), wat een speciale vorm van Linear Programming (LP) is. Aangenomen althans dat je alleen de lineaire vergelijkingen (matrix) hoeft op te stellen en daarna IP-software mag gebruiken om ze op te lossen.
Hydrogen economy is a Hype.

#11

A.Square

    A.Square


  • >250 berichten
  • 251 berichten
  • Ervaren gebruiker

Geplaatst op 05 oktober 2007 - 20:09

Fred, jouw denkrichting heb ik nog niet gehoord maar ik zal me volgende week even inlezen op IP. Dan laat ik nog weten of dat vruhtbaar is.

Verder heb ik een tweede werkwijze bedacht na de opmerking van de opdrachtgever dat je er van uit mag gaan dat de percentages benodigde computerkracht geheeltallig zijn.
Dit maakt het probleem namelijk nog een stukje eindiger.

Hier de methode.
Gegeven een willekeurige input I: LaTeX
Met alle LaTeX in geheeltallige procenten.
Definieer een 'aantallen vector' A
LaTeX
Op plaats 1 staat dus het hoe vaak 1% voorkomt, op plaats twee het aantal keer dat 2% voorkomt ... etc.
Deze vector is eenvoudig te definieren vanwege het feit dat de percentages geheeltallig zijn. (100-dimensionaal)
Verder definieren we een 'gewicht vector' deze wordt simpelweg gegeven door:
LaTeX \
Het is eenvoudig in te zien dat het inproduct A.W voor iedere A het totaal benodigde percentage van de input geeft.
Zie ook dat als A.W<=100 dat de volledige input dat in één processor kan.

Nu kunnen we het probleem omschrijven als het vinden LaTeX zodanig dat alle volgende vergelijkingen kloppen.
LaTeX
LaTeX
LaTeX
LaTeX
LaTeX

Dit is echter alleen het omschrijven van het probleem, dit heeft niets met de oplossing te maken.

Veranderd door A.Square, 05 oktober 2007 - 20:11






0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures