Aufgabe 0503 vom Lehrstuhl Rucksack-Problem

Wenn Du Dir in der Lösung den Entscheidungsbaum ansiehst, siehst Du, dass nur die ganzzahligen Lösungen als "zulässig" markiert sind...alle nicht-ganzzahligen Teillösungen brauchst Du nur zum weiteren Aufteilen der Lösungen!

Wenn ich das also - wie ich's gewohnt bin - verzweige mit ganzen Gegenständen und die Rest-KG darstelle komme ich ja zum selben Ergebnis. Aber gilt das denn auch?
Mich verwirrt das 1/4 von Gegenstand 3 eher, da schreibe ich : restl. Gewicht: 1 kg

Die anteiligen Gegenstände brauchst Du schon, denn die sind ja der Entscheidungsfaktor für die nächste Verzweigung:
a) Gegenstand ganz mit rein
oder
b) Gegenstand ganz raus...

Wir habend das in der Klausurvorbereitung so gemacht:

1 mitnehmen - verbleibt Rest: 14 - 8 = 6 kg => also weiterverzweigen
1 nicht mitnehmen - verbleibt Rest: 14 kg => also weiterverzweigen
1 - mitnehmen - 2 mitnehmen: Rest: 6 - 5 = 1 kg, es gibt keinen derartigen Gegenstand, also STOP => terminiert
usw.
So habe ich das verstanden und rechne nicht mit Teilgegenständen und Pseudo-Teilnutzen, die gar nicht möglich sind, rum => es gibt ja schließlich keinen 1/4 Nutzen eines 1/4 Gegenstandes ... ich habe mit meinem Weg also nur mögliche Lösungen

es kommt wie gesagt aufselbe raus, mich wundert nur die Darstellung in der ML der Aufgabe. Deshalb die Befürchtung, dass mein Weg zwar zum Ergebnis kommt, aber nur Teilpunkte gibt, weil es anders gefordert wird vom Lehrstuhl

Ob der Lehrstuhl Deine Lösung voll bepunktet, weiss wohl nur der Lehrstuhl 😀

Aber ich sehe die Darstellung so, dass durch den anteiligen Gegenstand die nächste Entscheidungsregel (dabei/nicht dabei) formuliert wird.

Sonst würdest Du ja willkürlich Gegenstände dazu packen oder raus lassen...

P.S.: Frau Rudolph ist übrigens sehr nett - stell die Frage doch mal in der Newsgroup

Gute Idee - Frage ist gestellt.
Ich berichte über die Antwort

Vom Lehrstuhl habe ich noch keine Antwort - aber bei der Übungsaufgabe 0507 habe ich folgenden Hinweis gefunden: "Als Relaxation wird auf die Ganzzahligkeitsbedingung verzichtet."
Heißt: Die Ganzzahligkeit wird als Bedingungen in diesem Optimierungsmodell weggelassen, um ein einfacher lösbares Modell zu erhalten, welches das ursprüngliche Problem enthält. So gilt als eine Relaxation bei Branch&Bound in OR das Weglassen der Ganzzahligkeitsbedingung als Vereinfachung. Wenn das so ist und mich die Vereinfachung nur verwirrt, spricht doch eigentlich nichts dagegen, es ohne die Vereinfachung zu lösen *find*

Heute - am Sonntag ! *wow* - gab's eine Antwort des Lehrstuhls:

...
Die Vorgehensweise in der Klausurvorbereitung klingt im Übrigen eher nach einer vollständigen Enumeration. Dass Sie zu derselben Lösung gelangen, liegt auf der Hand, allerdings dürfte der Aufwand beträchtlich sein.
...

und der Tipp es wie in der ML zu machen.
Ich gebe ja zu, wenn man sich damit ein paar Mal auseinandergesetzt hat, gehts ebenso. Also übe ich halt noch die "Teilnutzen"