Kombinatorische Verschnittoptimierung

[Kopfkratzer]

Hallo zusammen,

diese Frage richtet sich vermutlich in erster Linie an fortgeschrittene Mathematiker:

Gegeben sind als Ausgangsware Stangen fester Länge. Nun gilt es, aus diesen Stangen eine Vielzahl kleinerer Stangen zu schnippeln. Dabei soll möglichst geringer Verschnitt entstehen.

Meine Frage nun: Wie lassen sich derlei Aufgaben (eindimensionale Verschnittoptimierung) mathematisch am besten lösen. Ich kenne wohl Programme, die solche Aufgaben erledigen, weiß aber nicht genau, wie deren Algorithmen funktionieren. Natürlich könnte ein Rechner spielend alle möglichen Kombinationen durchspielen und so die beste Variante ermitteln. Ich suche aber nach einer geschickteren Lösung.

Kann mir da zufällig jemand auf die Sprünge helfen?

Beste Gruß
Kopfkratzer

[wahsaga]

hi,

Gegeben sind als Ausgangsware Stangen fester Länge. Nun gilt es, aus diesen Stangen eine Vielzahl kleinerer Stangen zu schnippeln. Dabei soll möglichst geringer Verschnitt entstehen.

Meine Frage nun: Wie lassen sich derlei Aufgaben (eindimensionale Verschnittoptimierung) mathematisch am besten lösen.

Mathematisch wäre das wohl eine Extremwert-Aufgabe, wenn ich nicht alles aus Schulzeiten vergessen habe.

Ich kenne wohl Programme, die solche Aufgaben erledigen, weiß aber nicht genau, wie deren Algorithmen funktionieren.

Algorithmisch wäre vielleicht Backtracking ein passendes Stichwort.

gruß,
wahsaga

[Kopfkratzer]

Mathematisch wäre das wohl eine Extremwert-Aufgabe, wenn ich nicht alles aus Schulzeiten vergessen habe.

Ja, Extremwert-Aufgabe klingt gut - kann mich sogar noch entsinnen, was das ist. Nur wie genau soll das zu berechnen sein? Ich finde da einfach keinen konkreten Lösungsansatz.

Algorithmisch wäre vielleicht Backtracking ein passendes Stichwort.

Backtracking folgt doch im Wesentlichen dem Trial-And-Error-Prinzip, wenn ich da richtig liege. Ich hatte mir allerdings erhofft, dass es geschicktere Ansätze für dieses Problem gibt.

Salut
Kopfkratzer

[Cruz]

Hallo,

Mathematisch wäre das wohl eine Extremwert-Aufgabe...
Ja, Extremwert-Aufgabe klingt gut

ich glaube, dass man sich hier mit einem rein mathematischen Ansatz die Zähne ausbeisst.

Erstens mal besteht der Lösungsraum aus der Kombinatorischen Vielfalt der möglichen Verteilungen der kleinen auf die großen Stangen. Das ist kein Raum, den man etwa in ein Koordinatensystem einzeichnen kann. Ich kann nicht mal wirklich eine Dimension für diesen Raum angeben.

Hinzukommt, dass die Funktion Verschnitt(x), wobei x irgendeine mögliche Aufteilung der Stangen ist, nicht stetig ist. Man kann sie sich sehr gut als Treppenlandschaft über den oben beschriebenen Lösungsraum vorstellen. Das ist deswegen so, weil viele Lösungen den gleichen Verschnitt produzieren und der Verschnitt (also der Funktionswert) sich nur dann ändert, wenn man eine a-Stange komplett ausspart oder eben hinzunimmt.

Gruß,
Cruz

[seth_not@home]

gudn tach!

Gegeben sind als Ausgangsware Stangen fester Länge. Nun gilt es, aus diesen Stangen eine Vielzahl kleinerer Stangen zu schnippeln. Dabei soll möglichst geringer Verschnitt entstehen.

ich habe das jetzt so verstanden:
du hast n stangen, die alle die gleiche laenge a haben. und du willst moeglichst viele kleine stangen der laenge b, wobei b<a.

aber die loesung dafuer ist nicht kompliziert:
max_anz_stangen = n*floor(a/b)
verschnitt ist dabei schon minimal, naemlich n*(a mod b).

wahrscheinlich habe ich dich bloss falsch verstanden. was genau moechtest du?
interessant wird es eigentlich erst, wenn a und b nicht konstant sind. und sollen moeglichst viele kleine stangen hergestellt werden? oder ist vorgegeben, wieviele kleine stangen geschnippelt werden sollen und es ist nur der verschnitt zu minimieren?

prost
seth

[Kopfkratzer]

interessant wird es eigentlich erst, wenn a und b nicht konstant sind. und sollen moeglichst viele kleine stangen hergestellt werden? oder ist vorgegeben, wieviele kleine stangen geschnippelt werden sollen und es ist nur der verschnitt zu minimieren?

Du hast Recht, ich hab mich da etwas unklar ausgedrückt. a kann schon konstant sein, aber b eben nicht.

Nehmen wir ein Beispielt:

a = 50 Meter
b = 1 - 30 Meter

Wenn jetzt von einer a-Stange noch 5 Meter übrig sind, wäre es z.B. sinnvoll, eine 4,5er-Stange (b) vom nächsten "a" abzusäbeln, da ich sonst 0,5 Meter Verschnitt hätte.

Die verschiedenen b-Stangen sind zwar in Ihrer jeweiligen Länge bekannt, aber eben nicht die Reihenfolge, mit der sie von den a-Stangen abgeschnitten werden. Das gilt es zu ermitteln.

Hoffe jetzt ist es etwas klarer.

Salut
Kopfkratzer

[Daywalker]

Nehmen wir ein Beispielt:

a = 50 Meter
b = 1 - 30 Meter

Wenn jetzt von einer a-Stange noch 5 Meter übrig sind, wäre es z.B. sinnvoll, eine 4,5er-Stange (b) vom nächsten "a" abzusäbeln, da ich sonst 0,5 Meter Verschnitt hätte.

Wie jetzt? Wäre es sinnvoll, damit du "nur" 0,5 Meter Verschnitt hast, oder wäre es eher nicht sinnvoll, da du sonst 0,5 Meter Verschnitt hast.

Die verschiedenen b-Stangen sind zwar in Ihrer jeweiligen Länge bekannt, aber eben nicht die Reihenfolge, mit der sie von den a-Stangen abgeschnitten werden. Das gilt es zu ermitteln.

Es gibt keine Lösung in der Form, dass du einfach nur die Länge der aktuellen Stange in eine Funktion reintust, und als Antwort die Lösung "Abschneiden von Stange X" erhälst.

Du benötigst erstens schon mal zwingend alle abzuschneidenden Stangen auf einmal.

Weiterhin wird der Algorithmus ein "Probieralgorithmus" sein, d.h. er wird Annahmen treffen und testweise Lösungen ermitteln, solange bis er ein Optimum gefunden hat.

Das wiederum bedeutet: Du mußt erstmal definieren, was für dich optimal denn überhaupt bedeutet?

Bei nur einer einzigen A-Stange hast du kein Optimierungsproblem. Der Rest von A bleibt eben übrig - Pech.

Aber schon bei zwei A-Stangen ist die Frage, was du als optimal beim Verschnitt betrachtest.

Angenommen, die A-Stange ist 10 Meter lang (zwei Stück also 20 lfd Meter). Jetzt willst du folgende Stücke schneiden:
2x 5 Meter
2x 3 Meter

Mögliche Ergebnisse:
Stange 1 wird komplett aufgebraucht, Stange 2 hinterläßt einen Rest von 4 Metern. Oder beide Stangen werden zu jeweils 8 Metern genutzt und hinterlassen jeweils 2 Meter Rest.

Die Frage ist eben: Kann man mit einem einzigen 4-Meter-Rest mehr anfangen, als mit zwei 2-Meter-Resten? Was ist wünschenswerter?

Und wenn wir das Beispiel noch etwas modifizieren, und statt 2x 3 Metern einfach 2x 4 Meter abschneiden, dann bleiben entweder 1x 2 Meter Rest, oder 2x 1 Meter.

Wenn nun aber sowohl der 2-Meter-Rest, als auch der 1-Meter-Rest im Müll landen würden - ist es dann notwendig, den Verschnitt bis ins letzte zu optimieren?

[Kopfkratzer]

Nehmen wir ein Beispielt:

a = 50 Meter
b = 1 - 30 Meter

Wenn jetzt von einer a-Stange noch 5 Meter übrig sind, wäre es z.B. sinnvoll, eine 4,5er-Stange (b) vom nächsten "a" abzusäbeln, da ich sonst 0,5 Meter Verschnitt hätte.

Wie jetzt? Wäre es sinnvoll, damit du "nur" 0,5 Meter Verschnitt hast, oder wäre es eher nicht sinnvoll, da du sonst 0,5 Meter Verschnitt hast.

Schnippel ichs von besagter a-Stange ab, wärs nicht sinnvoll, da die 0,5 garantiert Verschnitt wären. Schnippel ichs von der nächsten (noch kompletten) a-Stange ab, hab ich zumindest noch die Chance, ohne Verschnitt auszukommen.

Es gibt keine Lösung in der Form, dass du einfach nur die Länge der aktuellen Stange in eine Funktion reintust, und als Antwort die Lösung "Abschneiden von Stange X" erhälst.

Du benötigst erstens schon mal zwingend alle abzuschneidenden Stangen auf einmal.

Ja, vermutlich. Oder eben Wahrscheinlichkeiten auf Basis historischer Werte...(aber das ist schon ein anderes Thema). Sagen wir einfach,  Anzahl und Länge der einzelnen b-Stangen sind bekannt.

Weiterhin wird der Algorithmus ein "Probieralgorithmus" sein, d.h. er wird Annahmen treffen und testweise Lösungen ermitteln, solange bis er ein Optimum gefunden hat.

Das hatte ich befürchtet. ;-)

Das wiederum bedeutet: Du mußt erstmal definieren, was für dich optimal denn überhaupt bedeutet?

Das wissen wir schon. Optimal = minimaler Verschnitt.

Bei nur einer einzigen A-Stange hast du kein Optimierungsproblem. Der Rest von A bleibt eben übrig - Pech.

Aber schon bei zwei A-Stangen ist die Frage, was du als optimal beim Verschnitt betrachtest.

Angenommen, die A-Stange ist 10 Meter lang (zwei Stück also 20 lfd Meter). Jetzt willst du folgende Stücke schneiden:
2x 5 Meter
2x 3 Meter

Mögliche Ergebnisse:
Stange 1 wird komplett aufgebraucht, Stange 2 hinterläßt einen Rest von 4 Metern. Oder beide Stangen werden zu jeweils 8 Metern genutzt und hinterlassen jeweils 2 Meter Rest.

Die Frage ist eben: Kann man mit einem einzigen 4-Meter-Rest mehr anfangen, als mit zwei 2-Meter-Resten? Was ist wünschenswerter?

Natürlich in diesem Fall die 4 Meter. Damit kann man IN JEDEM FALL mehr anfangen.

Und wenn wir das Beispiel noch etwas modifizieren, und statt 2x 3 Metern einfach 2x 4 Meter abschneiden, dann bleiben entweder 1x 2 Meter Rest, oder 2x 1 Meter.

Auch hier ganz klar: 1x2 Meter ist IN JEDEM FALLE besser als 2x1 Meter. Logisch, oder?

Wenn nun aber sowohl der 2-Meter-Rest, als auch der 1-Meter-Rest im Müll landen würden - ist es dann notwendig, den Verschnitt bis ins letzte zu optimieren?

Das ist richtig. In der Praxis müsste man praktisch eine Müll-Grenze definieren, also eine Länge, die 100%ig nicht mehr zu gebrauchen ist. Für meinen Fall ist das aber unerheblich. Hier ist das Ziel immer, möglichst viele a-Stangen komplett und ohne jeglichen Verschnitt aufzubrauchen.

Salut
Kopfkratzer

[Daywalker]

Wenn jetzt von einer a-Stange noch 5 Meter übrig sind, wäre es z.B. sinnvoll, eine 4,5er-Stange (b) vom nächsten "a" abzusäbeln, da ich sonst 0,5 Meter Verschnitt hätte.

Wie jetzt? Wäre es sinnvoll, damit du "nur" 0,5 Meter Verschnitt hast, oder wäre es eher nicht sinnvoll, da du sonst 0,5 Meter Verschnitt hast.

Schnippel ichs von besagter a-Stange ab, wärs nicht sinnvoll, da die 0,5 garantiert Verschnitt wären. Schnippel ichs von der nächsten (noch kompletten) a-Stange ab, hab ich zumindest noch die Chance, ohne Verschnitt auszukommen.

Das funktioniert aber nur, wenn du garantiert weißt, welche weitere Stangenlänge nach dieser 4,5-Meter-Stange noch gebraucht wird.

Wenn keinerlei weitere Stange benötigt wird, hast du 5 Meter Verschnitt von der ersten und 45,5 Meter Verschnitt von der zweiten Stange. Das ist deutlich mehr, als 0,5 Meter von der ersten und keinerlei Verschnitt von der zweiten Stange.

Du benötigst erstens schon mal zwingend alle abzuschneidenden Stangen auf einmal.
Ja, vermutlich. Oder eben Wahrscheinlichkeiten auf Basis historischer Werte...(aber das ist schon ein anderes Thema). Sagen wir einfach,  Anzahl und Länge der einzelnen b-Stangen sind bekannt.

Das ist zwingend notwendig. Du kennst sowohl Anzahl als auch Länge aller abzuschneidender Stangen.

Wenn das nicht so wäre, sondern du aus laufender Produktionsanforderung die Aufgabe hast, aus den A-Stangen unter Vermeidung von überflüssig viel Verschnitt, aber mit unbegrenzter Zahl von A-Stangen beliebig viele B-Stangen zu generieren, würde ich Längenklassen bilden.

Eine A-Stange kriegt dann einfach ein Label "Aufteilen in X Stücke der Länge Y", und jede Stange, die in diese Längenklasse fällt, wird dann halt von der (angefangenen oder neu anzufangenden) A-Stange abgeschnitten. Bei 50-Meter-Stangen würde beispielsweise eine Längenklasse 50 bis 100 cm existieren, d.h. es würden maximal 50 Stangen abschneidbar sein, und maximal wären 49 cm Verschnitt.

Klar, wenn du historische Daten der typischen Längenverteilung hast, kannst du natürlich auch eine durchschnittliche Tagesproduktion analysieren und ermitteln, dass ein 5,0-Meter-Rest wahrscheinlich noch für ein 4,99-Meter-Stück gebraucht wird, weshalb das jetzt benötigte 4,5-Meter-Stück lieber von einer neuen A-Stange geschnitten wird.

Andererseits: Hast du denn unbegrenzt Nachschub? Doch wohl eher nicht. Und unbegrenzt Lagerkapazität für angeschnittene Stangen auch nicht. Und unbegrenzt Zeit, eine irgendwann früher angebrochene Stange, die jetzt gerade exakt ohne Verschnitt passen würde, wiederzufinden, auch nicht.

Das wiederum bedeutet: Du mußt erstmal definieren, was für dich optimal denn überhaupt bedeutet?
Das wissen wir schon. Optimal = minimaler Verschnitt.

Wie gesagt, "minimaler Verschnitt" ist nicht ausreichend. Meine beiden Beispiele haben jeweils exakt 4,0 Meter Verschnitt übrig, weniger geht nicht. Die Optimierungsaufgabe benötigt weitere Regeln, wie beispielsweise "Minimale Anzahl von A-Stangen" oder "Möglichst große Reststücke".

Und wenn wir das Beispiel noch etwas modifizieren, und statt 2x 3 Metern einfach 2x 4 Meter abschneiden, dann bleiben entweder 1x 2 Meter Rest, oder 2x 1 Meter.
Auch hier ganz klar: 1x2 Meter ist IN JEDEM FALLE besser als 2x1 Meter. Logisch, oder?

Nein, das ist nicht unbedingt logisch. Es ergibt sich erst aus deinen weiteren, zu definierenden Bedingungen.

Angenommen, es werden sowieso nur Stangenlängen von 5 und 4 Metern benötigt, der Müllcontainer hat aber nur Platz für maximal 1,50 Meter lange Stangen, dann müßtest du die 2-Meter-Reste vor der Entsorgung nochmal durchschneiden. Deine "logische" Optimierung würde also in Wirklichkeit eine Verschlechterung sein, weil die Säge einen Schnitt mehr machen müßte und somit stärker abgenutzt wird.

Das ist richtig. In der Praxis müsste man praktisch eine Müll-Grenze definieren, also eine Länge, die 100%ig nicht mehr zu gebrauchen ist. Für meinen Fall ist das aber unerheblich. Hier ist das Ziel immer, möglichst viele a-Stangen komplett und ohne jeglichen Verschnitt aufzubrauchen.

Wie oben erwähnt: Es ist sicherlich möglich, eine Statistik aufzustellen mit den benötigten Längen aller zu produzierenden Abschnitte. Und diese Abschnitte, sofern sie denn in unendlicher Zahl benötigt werden, lassen sich sicherlich ziemlich optimal so verteilen, dass die verfügbaren Stangen optimal genutzt werden. Aber eben nur, wenn die Randbedingungen und Optimierungsforderungen vollständig bekannt sind.

[Kopfkrater]

Wir schweifen etwas ab. ;-)

Ich machs einfach mal ganz konkret:

a-stangen = je 50 Meter (unbegrenzt vorhanden)
b-stangen = 5,10,15,3,21,45,33,14,26,2,1,33,28,19,7,9,10 Meter

Es geht also nicht um Lagekapazitäten oder die Größe des Müllcontainers, sondern einfach nur darum, die ganzen b-stangen mit einem Minimum an Verschnitt zu produzieren. ;-)

Salut
Kopfkratzer

[Daywalker]

Wir schweifen etwas ab. ;-)

Richtig... :)

Ich machs einfach mal ganz konkret:

Das ist gut.

a-stangen = je 50 Meter (unbegrenzt vorhanden)
b-stangen = 5,10,15,3,21,45,33,14,26,2,1,33,28,19,7,9,10 Meter

Es geht also nicht um Lagekapazitäten oder die Größe des Müllcontainers, sondern einfach nur darum, die ganzen b-stangen mit einem Minimum an Verschnitt zu produzieren. ;-)

Die offensichtliche Lösung ist, alle möglichen Kombinationen von Schnittmustern sowie den resultierenden Verschnitt zu berechnen und dann einfach die Lösung zu nehmen, die "optimal" ist.

Das Problem dieser Herangehensweise ist, dass der Rechenaufwand quadratisch steigt, d.h. jede weitere B-Stange verdoppelt die Anzahl der möglichen Lösungen und damit auch den Rechenaufwand.

Jede alternative Lösung spart Rechenzeit, indem nicht das absolute Optimum gefunden wird, sondern nur eines, mit dem man leben kann.

[Daniel Thoma]

Hallo Daywalker,

Das Problem dieser Herangehensweise ist, dass der Rechenaufwand quadratisch steigt, d.h. jede weitere B-Stange verdoppelt die Anzahl der möglichen Lösungen und damit auch den Rechenaufwand.

Mit einem Verfahren mit quadratischem Aufwand für das Problem könntest Du reich werden, aber leider ist der Aufwand, nach allem was man weiß, exponentiell. Du hast ja eigentlich auch genau das verhalten, exponentiellen Wachstums beschrieben.

Grüße

Daniel

[Daywalker]

Das Problem dieser Herangehensweise ist, dass der Rechenaufwand quadratisch steigt, d.h. jede weitere B-Stange verdoppelt die Anzahl der möglichen Lösungen und damit auch den Rechenaufwand.
Mit einem Verfahren mit quadratischem Aufwand für das Problem könntest Du reich werden, aber leider ist der Aufwand, nach allem was man weiß, exponentiell. Du hast ja eigentlich auch genau das verhalten, exponentiellen Wachstums beschrieben.

Ähm, ja. Richtig gelesen, falsch wiedergegeben. O(2^n) ist exponentiell. :)

[Kopfkratzer]

Ähm, ja. Richtig gelesen, falsch wiedergegeben. O(2^n) ist exponentiell. :)

Und genau darin liegt ja das Problem. Ich hatte eben gehofft, dass es evtl. effizientere Lösungsansätze gibt. "Pareto-optimale Ergebnisse" scheinen in diese Richtung zu gehen, aber um das beurteilen zu können, muss ich mich noch etwas eingehender mit der Materie beschäftigen. Meine Mathe-Kenntnisse sind doch schon arg eingerostet...;-)

Salut
Kopfkratzer

[Vinzenz Mai]

Hallo,

Gegeben sind als Ausgangsware Stangen fester Länge. Nun gilt es, aus diesen Stangen eine Vielzahl kleinerer Stangen zu schnippeln. Dabei soll möglichst geringer Verschnitt entstehen.

das hört sich nach dem "Rucksackproblems" an, siehe z.B:
Rucksackproblem in Wikipedia.

Freundliche Grüße

Vinzenz

[Frank (no reg)]

Hi,

Ich gehe davon aus, dass die langen Stangen exakt eine (1) feste Länge haben:

• die ideale Länge von kleinen Stangen (die Teilung durch jene muss ohne Rest bleiben)
• die ideale/maximale Menge von kleinen Stangen (theoretisch unendlich)
• beides zusammen (dito)
• keines von beiden (die Frage ist hinfällig)

Interessant wäre, wenn der Ausgangspunkt variabel wäre. D.h. die Stangen jede eine eigene unterschiedliche Länge haben. Aber das was so explizit nicht herausgestellt. In jenem Falle hört es sich wirklich nach diesem Rucksackproblem an.

Ciao, Frank

[Kopfkratzer]

Hi,

Ich gehe davon aus, dass die langen Stangen exakt eine (1) feste Länge haben:

• die ideale Länge von kleinen Stangen (die Teilung durch jene muss ohne Rest bleiben)
• die ideale/maximale Menge von kleinen Stangen (theoretisch unendlich)
• beides zusammen (dito)
• keines von beiden (die Frage ist hinfällig)

Interessant wäre, wenn der Ausgangspunkt variabel wäre. D.h. die Stangen jede eine eigene unterschiedliche Länge haben. Aber das was so explizit nicht herausgestellt. In jenem Falle hört es sich wirklich nach diesem Rucksackproblem an.

Wie schon an anderer Stelle geschrieben, hatte ich mich etwas unpräzise ausgedrückt. Ja, die kleinen Stangen sind in Ihrer Länge unterschiedlich (allerdings vorgegeben). Das Rucksackproblem trifft es eigentlich ziemlich genau, obwohl in meinem Fall nicht mal ein Nutzenwert zu berücksichtigen ist. Es geht einfach nur darum, möglichst wenig Verschnitt zu produzieren oder - um im Bild zu bleiben - auf Teufel komm raus den Rucksack bis an den Rand zu füllen. ;-)

Danke jedenfalls für den Tipp - mal schauen, ob ich das durchblicke...;-)

Salut
Kopfkratzer

[Daniel Thoma]

Hallo Kopfkratzer,

Bin-Packing geht auch in die Richtung Deines Problems.
Wenn das Problem zu groß wird, um per Backtracking gelöst zu werden, kommen heuristische Verfahren wie bspw. evolutionäre Algorithmen in Frage um eine brauchbare Lösung zu finden.

Grüße

Daniel

[Andreas Pflug]

Hallo,

ich würde es mal mit 'simulated annealing'-Verfahren bzw. dem
'Metropolis-Algorithmus' versuchen
http://de.wikipedia.org/wiki/Metropolisalgorithmus

Du benötigst dann eine Funktion, die aus einer gegebenen
Reihenfolge jeweils den Verschnitt (==> "Energie") berechnet
sowie eine weitere Funktion, mit der die Reihenfolge zufällig
modifiziert werden kann.

Das Verfahren garantiert zwar generell nicht, dass das
absolute Optimum gefunden wird, dennoch werden auch bei
sehr großen Problemstellungen relativ schnell Lösungen
gefunden, die nahe am Optimum sind.

Viele Grüße

Andreas

[Cruz]

Hallo Kopfkratzer,

a-stangen = je 50 Meter (unbegrenzt vorhanden)
b-stangen = 5,10,15,3,21,45,33,14,26,2,1,33,28,19,7,9,10 Meter

in all dem Vorschlagssalat in diesem Thread ist meiner Meinung nach das 0-1-Rucksackproblem der richtige, den ich noch etwas ergänzen möchte. Betrachte jede a-Stange als einen einzelnen Rucksack und pack sie mit einem Greedy Ansatz der Reihe nach mit kleinen Stangen voll. Ganz konkret:

Pack einen optimalen Rucksack der Größe a aus allen verfügbaren b-Stangen und entferne die b-Stangen, die in den Rucksack gekommen sind. Wiederhole diesen Schritt, bis keine b-Stangen mehr verfügbar sind.

Das Verfahren läuft in O(n^3) und ist meiner Meinung nach optimal. Ich grübele noch an dem Beweis bzw. Gegenbeispiel.

Gruß,
Cruz

[Cruz]

Hallo

Versuchen wir es mit einem Widerspruchsbeweis.

Mit dem obigen Verfahren erhältst du als Ergebnis eine Reihe von "gepackten" a-Stangen mit steigendem Verschnitt. Es kann niemals passieren, dass eine a-Stange in einem späteren Schritt des Verfahrens besser gepackt wird, als eine andere a-Stange in einem frühren Schritt des Verfahrens, denn in diesem früheren Schritt standen alle b-Stangen zur Verfügung, die bei dem späteren Schritt genutzt wurden. Also ist die letzte a-Stange am schlechtesten verpackt und auf die konzentrieren wir uns.

Angenommen das Verfahren sei nicht optimal. Dann existiert eine andere Verteilung der b-Stangen, sodass du eine b-Stange (nennen wir sie b*) aus der _letzten_ gepackten a-Stange rausholen und in irgendeine andere a-Stange legen kannst. Diese b*-Stange muss die _einzige_ b-Stange in der letzten gepackten a-Stange sein, sonst würde sich der Gesamtverschnitt ja nicht ändern und die Lösung hätte sich durch die Umverlagerung nicht verbessert. Nur wenn die letzte a-Stange dadurch wirklich überflüsig wird, können wir den Verschnitt reduzieren.

Wir bringen also b* irgendwie in den anderen a-Stangen unter und schmeissen die letzte a-Stange weg. Daruch hat sich der Gesamtverschnitt in den restlichen a-Stangen reduziert. Dafür ist es notwendig, dass mindestens eine a-Stange (a*) jetzt besser gepackt ist, als vorher. Beim packen von a* stand b* allerdings zur Verfügung, also hätte der Rucksack Packer b* mit in a* reinpacken müssen. Ergo kann b* in keine andere a-Stange verlagert werden und das Verfahren hat eine optimale Lösung gefunden.

Sieht jemand einen Denkfehler?

Cruz

[Daniel Thoma]

Hallo Cruz,

Pack einen optimalen Rucksack der Größe a aus allen verfügbaren b-Stangen

Dieser Schritt mit einem Greedy-Verfahren ist in O(2^n). Es kann eben sein, dass bereits das erste Element falsch gewählt ist, dass Du in den Rucksack packst und Du damit alle Elemente wieder Rauswerfen musst.

Das Verfahren läuft in O(n^3) und ist meiner Meinung nach optimal.

Optimal ist es wohl, nur ist es leider nicht in O(n^3). Das wäre auch bei einem Problem, dessen Entscheidungsvariante NP-Hart ist, eher überraschend...

Man kann das Problem sicher auf ein Rucksack-Problem zurückführen, nur hat man damit die Problemstellung analysiert, aber noch keine Lösung gefunden.
Man kann eigentlich nur hoffen, dass das Problem klein ist oder sich mit Näherungsverfahren behelfen.

Grüße

Daniel

[Cruz]

Hallo Daniel,

Pack einen optimalen Rucksack der Größe a aus allen verfügbaren b-Stangen

Dieser Schritt mit einem Greedy-Verfahren ist in O(2^n).

Mit Greedy schon, aber mit der dynamischen Programmierung, ein Verfahren das Hand in Hand mit dem Rucksackproblem gelehrt wird, lässt sich ein Rucksack in O(n^2) packen. Wir haben maximal n viele Rucksäcke zu packen, daraus ergibt sich eine Laufzeit in O(n^3).

Der Greedy Anteil meines Vorschlag war nicht das packen eines einzelenen Rucksacks, sondern der Ansatz, dass man stets versucht jeden einzelnen Rucksack so voll wie möglich zu packen.

Optimal ist es wohl, nur ist es leider nicht in O(n^3). Das wäre auch bei einem Problem, dessen Entscheidungsvariante NP-Hart ist, eher überraschend...

Nein es ist nicht NP-Hart. Der Rucksack Problem ist nicht NP-Hart, weil es sich mit dynamischer Programmierung in polynomieller Zeit lösen lässt.

Man kann das Problem sicher auf ein Rucksack-Problem zurückführen, nur hat man damit die Problemstellung analysiert, aber noch keine Lösung gefunden.

Mein erstes Posting enthielt einen Algorithmus, der das Problem durch wiederholtes Anwenden eines Rucksack Lösers eine vollständige Lösung errechnet.

Viele Grüße,
Cruz

[Daniel Thoma]

Hallo Cruz,

Mit Greedy schon, aber mit der dynamischen Programmierung, ein Verfahren das Hand in Hand mit dem Rucksackproblem gelehrt wird, lässt sich ein Rucksack in O(n^2) packen.

Ah ja, stimmt. Das funktioniert allerdings nur bei ganzzahligen Gewichten.
Das verfahren iteriert ja über die Anzahl der Elemente und die Größe des "Rucksacks". Streng genommen ist das Verfahren also in O(n*m) wobei n die Anzahl der Elemente und m die Größe ist.
Für das Stangenproblem kann man nun einfach in einer ausreichend kleinen Einheit ganzzahlig arbeiten bzw. die Längen (rationale Längen vorausgesetzt, aber dass die nicht rational sein könnten, ist mathematische Spielerei) mit dem Hauptnenner erweitern.
Dieser Hauptnenner kann allerdings exponentiell groß werden:
Beweis: Alle Längen haben als Nenner Primzahlen. Damit ist der Hauptnenner das Produkt dieser Primzahlen, also > 2^n.

Die NP-härte verschwindet also durch die Annahme der Ganzzahligkeit. Bleibt die Frage, ob das Problem ganzzahlig Lösbar ist, oder ob m dabei zu groß wird.

Grüße

Daniel

[Cruz]

Hallo Daniel,

Das funktioniert allerdings nur bei ganzzahligen Gewichten.

Hm das bringt mich jetzt zum Nachdenken. Ich kann diese Aussage nicht widerlegen, aber mein Gefühl sagt mir, dass die Gewichte auch reelle Größen sein könnten. Also n ist die Anzahl der Gegenstände und m ist die Größe des Rucksacks, die hochiteriert wird. m könnte doch eine Disktretisierung eines von mir aus pi großen Rucksacks sein. Man iteriert über diese Diskretisierung. Die Summe der betrachteten Gegenstände (eine reelle Zahl also) muss <= m sein, damit sie in den Rucksack passen und das ist ja kein Problem.

Also wenn überhaupt, dann müsste der Rucksack und nicht die Gewichte ganzzahling teilbar sein. Kann die Disktretisierung unter Umständen eine optimale Lösung verhindern? Vielleicht muss sie eine Bedingung erfüllen, wie z.B. dass die Schrittlänge zwischen den Größen kleiner sein muss, als das kleinste Gewicht.

Aber mal abgesehen davon, dass es uns Informatikern Spaß macht sich auch die letzten Nuancen zu überlegen, ist für das vom OP gestellte Optimierungsproblem eine centimeterweise Iterierung über die Länge der a-Stangen sicherlich ausreichend. :)

Viele Grüße,
Cruz

[Daniel Thoma]

Hallo Cruz,

Naja, das Problem "Kann der Rucksack so gepackt werden, dass ein Nutzen >= x erreicht wird" ist erwiesener maßen NP-Hart.
Das Optimierungsproblem "Berechne den größten Nutzen" kann man ja ganz trivial in das Entscheidungsproblem umbauen. Man Optimiert einfach, und guckt ob es reicht.

Nun haben wir einen Algorithmus, der das Problem in O(n^2) löst.
Es gibt also zwei Möglichkeiten:
1. der Algorithmus funktioniert nur für eine eingeschränkte Variante des Problems
2. Wir haben einen Beweis für P = NP gefunden (möglich, aber unwahrscheinlich, vor allem da der Algorithmus schon lange bekannt ist ;)

Also wenn überhaupt, dann müsste der Rucksack und nicht die Gewichte ganzzahling teilbar sein.

Wenn man den Algorithmus sieht, wird da eine n x B Matrix (B ist die Schranke Größe) aufgebaut, also muss B schonmal ganzzahlig sein.
Die Größe der Elemente w(i) wird allerdings verwendet, um auf Einträge dieser Matrix zuzugreifen. Muss also auch ganzzahlig sein.
Man kann sich nun natürlich überlegen, ob man an der ein oder anderen Stelle vielleicht runden oder sonstwie rumtricksen könnte, aber wenn man den Algorithmus so anwenden will, wie er da steht, muss man irgendwie ganze Zahlen bekommen.
Das erreicht man, indem man sich ein Raster wählt, in das sowohl B also auch alle w(i) reinpassen, und letzteres ist entscheidend.
Damit braucht man ein Raster von einer Größe, die durch alle Nenner teilbar ist und das ist dann eben exponentiell groß.
Ich sehe an dieser Argumentation (natürlich ist es kein Beweis, dass es nicht geht, der dürfte schwierig sein) auf den ersten Blick keine Schwäche.

Kann die Disktretisierung unter Umständen eine optimale Lösung verhindern? Vielleicht muss sie eine Bedingung erfüllen, wie z.B. dass die Schrittlänge zwischen den Größen kleiner sein muss, als das kleinste Gewicht.

Wie diskretisierst Du die Gewichte? Runden? Die Fehler schaukeln leicht so auf, dass eine andere, oder gar eine unmögliche Lösung optimal wird:
Gewichte: 4 x 1/3
Maximale Länge: 1
Schrittweite: 1/4 (sieht also kein genug aus)
Es werden allso alle Gewichte gerundet auf 1/4. Und schon passen alle Elemente rein.

Aber mal abgesehen davon, dass es uns Informatikern Spaß macht sich auch die letzten Nuancen zu überlegen, ist für das vom OP gestellte Optimierungsproblem eine centimeterweise Iterierung über die Länge der a-Stangen sicherlich ausreichend. :)

Naja, hm 1 m minimale Elementlänge, 50 m Gesamtlänge. Dann würdest Du also Größenordnungsmäßig 50 * 5000 = 250000 Schritte machen. Geht sicher noch, elegant ist das aber nicht und die Lösung ist noch nicht mal exakt, wenn er nicht sowieso nur mit cm-Genauigkeit arbeiten will.
Besser als alle Kombinationen durchzuprobieren, ist der Ansatz natürlich noch und an ein heuristisches Verfahren kommt man damit sicher auch locker ran.

Grüße

Daniel