Operations Research 1

at RWTH Aachen

Join course
893
Next exam
FEB 14
Discussion
Documents
Flashcards
KORREKTUR: yj
<= 1 weil nicht jeder Auto fahren muss
Muss nicht noch eine Variable eingeführt werden, die sagt ob ein Auto benutzt wurde? Wie im Tutorium?
Das sollte nicht nötig sein, da es hier keine Kosten für die Nutzung des Autos gibt und kein Constraint diese Nutzung einschränkt.
Warum wird hier ein "h" eingefügt? Was ist der Sinn dahinter?
View 3 more comments
damit Städten nicht besucht werde, wo es kein Konzert stattfinden wird
No area was marked for this question
Ich habe noch einige Probleme das zustande kommen dieser Tabellen zu verstehen. Zur Aufgabe 2a : Bei Knoten 5 erhöht sich doch der Lower bound in der Tabelle. da Knoten 2 fertig betrachtet wurde. Also bildet man das Minimum der offenen subproblems. Wäre das dann das Minimum von Knoten 5, 3, 7?
Knoten 7 hast du zu diesem Zeitpunkt noch nicht besucht, entsprechend das Minimum von knoten 3 und 5
Woher kommt die Reihenfolge der Knoten? 1 - 2 -3 und dann 5 - 4, warum nicht 4 - 5?
ist dir selbst überlassen, welches Subproblem du zuerst betrachtest
Weiß jemand was in der Aufgabe gemeint sein könnte? 1.b
View 1 more comment
aber bei diesen beiden Ungleichungen kommt doch dann wieder eine andere nicht ganzzahlige Lösung als optimale Lösung raus oder nicht?
Ja, aber die ist dann immerhin näher an der ganzzahligen Lösung. Ich verstehe auch nicht so recht worauf die in der Aufgabe hinauswollen.
warum hören wir hier auf?
weil die Lösung schlechter ist als die -14 von knoten 6. und innerhalb einer branches können wir nicht besser werden. Das heißt unter den Knoten 7 würde nichts besseres als -12 rauskommen
Ist schon klar was in Class Test 3 vorkommt?
View 2 more comments
Wie sicher ist das? Es sollte dann ja dazu eine offizielle Ankündigung geben wie bei den letzten male oder?
Mir wurde einfach nur gesagt dass es unfair wäre weil das erst jetzt im Tutorium besprochen wurde und das Freitags Tutorium zumindest dynamic programming nicht durchgenommen hat. Hab sie extra nochmal darauf angesprochen
Wieso ist 1 nicht Teil von V und was für einen Vorteil bringt es?
Das ist ja die Subtour-Elimination-Constraint. Die Menge S umfasst also alle möglichen Untergruppen von Städten in der Menge V. Damit du nicht irgendwo auf der Karte plötzlich im Kreis fährst, wird hier die Bedingung gesetzt, dass jede dieser Subtouren aus S Verknüpfungen zum Rest der Menge V hat. In diesem speziellen Fall will man aber immer von Stadt 1 losfahren und auch dort wieder enden. Daher muss man für diese Randbedingung die 1 ausschließen, da man ansonsten auch diesen Rundkurs verbieten würde
verstehe ich nicht so wirklich. Vom Knoten 1 (also wenn ich S=1 setze) aus muss Tij doch auch größergleich 2 sein?
Hat noch jemand keine Rückmeldung auf die 2. Gurobi Aufgabe bekommen? Die erste wurde ja sehr schnell korrigiert, bei der 2. haben wir aber noch keine Ergebnisse..
Bisher hat noch niemand, mit dem ich gesprochen habe ein Ergebnis...
Die Aufgabenstellung spricht von "consecutively visited locations" - wo wird das hier abgebildet?
x_i,j ist ja so definiert, dass du direkt nach i zu j fährst, falls x=1 ist. und da ja x_i,j mit _di,j multipliziert wird, werden nur die Strecken zwischen zwei nacheinander besuchten Orten betrachtet z kann dann wiederum nur den Wert 1 annehmen, falls diese Strecke überhaupt genutzt wird(x=1) und diese auch noch länger als 4min ist (d>=4) und das muss mindestens einmal gegeben sein
Könnte man hier auch schreiben <= 2Yj und dann den 2. constraint weglassen?
ja, vollkommen richtig
´Wieso wird hier die Möglichkeit nicht betrachtet item 4 und 6 durch 5 zu ersetzen? Dann würde man wieder auf ein Gesamtgewicht von 11 kommen, jedoch mit einem Profit von 34
die Nachbarschaft wurde in der Aufgabenstellung so definiert, dass man 1(!!) item hinzufügt, wegnimmt oder austauscht
warum ist bei node 11 zLP gleich 9? Man betrachtet doch das zLP von allen noch offenen subtrees, es ist keins mehr offen...
die untere SChranke ist zwingend immer kleiner als die obere Schranke. Im letzten schritt aktualisierst du dann deine untere Schranke auf den Wert der oberen, da ja die 8 nicht länger zu erreichen ist
Kann mir jemand erklären, warum von den Koordinaten (1.5, 3) ausgegangen wird und nicht z.B. von (4, 0.5)?
Der Pfeil des Normalenvektors ist falschrum eingezeichnet. (1,6) ist der Normalenvektor also schiebt man die gerade nach oben. Für die Vorstellung: liegt daran dass eine Minimierung mit nur negativen vorzeichen gleich einer maximierung von -f(x) ist.
Wie ergeben sich die LowerBounds? Also warum wird erst bei Knoten 5 der zLP zu 4 und nicht schon bei Knoten 3?
Da Knoten 3 bei Knoten 4 noch offen ist (Bei Knoten 4 sind noch die Knoten 2 und 3 offen, das Minimum der Werte liegt bei Knoten 2, also 3). Knoten vier ist dann auch ein integrales Optimum und Knoten 2 wird damit geschlossen. Dann sind nur noch Knoten 3 und Knoten 5 offen, das Minimum dieser beiden ist 4, sodass sich bei Knoten 5 die lower bound zu 4 ändert.
Woher kommt das f?
Ich meine der Tutor hat gesagt dass in dem von ihm gezeigten Aufgabentext manche Variablen anders benannt wurden (steht ja auch oben dass das aus 2018 ist). Könnte hier in dem Fall vielleicht das o sein? Das kommt ja auch ansonsten in der Lösung nicht vor.
wie sind die unterschiedlichen Knoten und die darüber stehenden Zahlen zu interpretieren?
View 2 more comments
Also muss in der Folge x2 anders gewählt werden. Hier also >=1 oder <=0. Wieder wird für beide Werte geguckt. Für x2 <= 0 ist das maximale x1 2,5 (kein Integer --> gestrichelter Kreis) mit ZF. Wert -7,5. Für x2>=1, ist unter der anderen Annahme x1 <= 3, der geringste x2 Wert 1. Entsprechend ergibt sich für Knoten 4 ein aus Intergern berechneter ZF Wert(voller Kreis) mit -8
Ich habe bei der Lösung versucht mich an die Konvention, die auf dem Blatt vorgestellt wurde, zu halten
Kurze Frage zur python Abgabe: ich habe die richtigen Ergebnisse. Allerdings werden die unter solution count aufgeführt ich bin jetzt etwas verwirrt ob das jetzt schon das richtige Ergebnis ist
Hallo zusammen, mal eine Frage an besonders diejenigen, die in den letzten Semestern schon erfolgreich waren: Wie habt Ihr Euch für die Klausur vorbereitet bzw. wie bereitet Ihr Euch vor? Ich bekomme da gerade irgendwie keinen Griff dran, weder Karteikarten noch eine Zusammenfassung wirken gerade sinnvoll, nur Aufgaben rechnen aber auch widerum nicht..
In der Klausur geht es darum die Aufgaben möglichst schnell und präzise zu lösen (wie man auch in den Testaten gesehen hat). Deswegen würde ich sagen, dass Aufgaben rechnen das Beste ist, was du tun kannst.
Ist das Python Zeug nur für den Bonus relevant oder kommt dazu auch eine Aufgabe in der Klausur?:)
In QM war es tatsächlich so, dass auch eine (Teil-)Aufgabe dazu in der Klausur kam...
Hallo zusammen, ich habe folgende Constraints aufgestellt. Leider bekomme ich als optimales Ergebnis 0 raus und verstehe nicht woran das liegt. Könnt ihr mir vielleicht weiterhelfen? :) for (u, v) in arcs: model.addConstr(quicksum(f[c,u,v] for c in commodities) <= capacities[u,v]*x[u,v]) model.addConstr(quicksum(x[u,v] for (u,v) in arcs) <= max_arcs) for c in commodities: for u in facilities: if u == source(c): model.addConstr(quicksum(f[c,u,v] for v in out_neighbors(u)) - quicksum(f[c,v,u] for v in in_neighbors(u)) == flow_amount(c)) elif u == target(c): model.addConstr(quicksum(f[c,u,v] for v in out_neighbors(u)) - quicksum(f[c,v,u] for v in in_neighbors(u)) == -flow_amount(c)) else: model.addConstr(quicksum(f[c,u,v] for v in out_neighbors(u)) - quicksum(f[c,v,u] for v in in_neighbors(u)) == 0)
View 1 more comment
Es mag dumm klingen aber habt ihr den Code abgespeichert, bevor ihr ihn habt laufen lassen? Außerdem hast du in der Flow Conservation Constraint bei c und u runde Klammern und keine eckigen verwendet, das müsstest du meines Wissens auch noch anpassen
Ohje hab eben ewig auf den Code gestarrt und das mit den eckigen Klammern nicht gesehen... Danke! :D
Leider komme ich bei der Flusserhaltungsbedingung nicht weiter und erhalte immer einen Fehler :( Habe sie wie folgt aufgestellt: for c in commodities: for u in facilities: if source[c] == u: model.addConstr(quicksum(f[c,u,v] for v in out_neighbors[f]) - quicksum(f[c,u,v] for v in in_neighbors[f]) == flow_amount[c]) elif target[c] == u: model.addConstr(quicksum(f[c,u,v] for v in out_neighbors[f]) - quicksum(f[c,u,v] for v in in_neighbors[f]) == - flow_amount[c]) else: model.addConstr(quicksum(f[c,u,v] for v in out_neighbors[f]) - quicksum(f[c,u,v] for v in in_neighbors[f]) == 0) Leider sagt Python mir immer "TypeError: unhashable type: 'dict'" - Kann mir da jemand weiterhelfen oder hat einen Tipp, woran es liegen könnte? Mit Google etc. komme ich nicht weiter, bin langsam echt verzweifelt. Habe auch leider absolut keine Vorkenntnisse im Programmieren, was es nicht grade einfacher macht :'D Danke schonmal <3!
View 5 more comments
Ja jetzt kommt das richtige raus, hab wohl auch noch u und v tauschen müssen wie oben vorgeschlagen wurde
Kannst du vielleicht deinen Code posten? ich bekomme als optimale Lösung irgendwie 0 raus und weiß nicht woran es liegt :(
Wann ist der letzte Class Test?
16.01
steht im Lernraum
weiß jemand wie viele Punkte man für den Bonus in er Klausur braucht? Also sowohl bei Gurobi als auch bei den Testaten?
75%
Moin, hat schon jemand die dritte Gurobi Aufgabe gemacht`? Ich verstehe die Bedingungen zu den maximalen Arcs und zu den Kapazitäten, aber ich weiß nicht, wie meine anderen Bedingungen aussehen. Also wie sag ich meinem Programm, es soll die Commodities von der Quelle ins Ziel transportieren? Wäre geil wenn mir jemand helfen könnte
würde hier jetzt nicht jeder Pfeil benutzt werden müssen der länger als 4 Minuten ist? ?? ginge nicht auch: sum(j=1bisn)sum(i=1bisn) über xij*dij >1 für alle dij>4 ??
Meiner Meinung auch nicht ganz richtig: muss aufgeteilt werden sum z über j = di für alle i sum z über i <= sj für alle j
View 2 more comments
In der Lösung mit aufgeteilten Summen wird z_ij doch nie den Wert Null annehmen, da die summe darüber = d_i ist - oder?
ja, die Bedingung summe(z_ij) über j = d_i für alle i verhindert, dass z_ij = 0 werden kann ...
Hey :-) Weiß jemand, welche Übungen und Tutorials für den Class Test am Donnerstag relevant sind?
View 1 more comment
ich vermute alles bis sheet 09, Task 23
Gestern im Tutorium wurde angedeutet, dass sinnvollerweise nicht nochmal dasselbe aus dem ersten Test abgefragt wird. Also gehe ich mal von scheduling, TSP und so aus.
Hey:) hat hier jemand die Lösung für die Programmieraufgabe? Ich habe es jetzt 2 Tage versucht aber bin scheinbar leider absolut zu unfähig dafür... wäre mir auch etwas wert.. Glühwein, Bier, Geld, ... mag doch nur diesen Bonus:(
View 1 more comment
Ich liebe dich!!!!!!!!!!!!!!!!!!!!!!!!!!
sehr nett! lieben Dank
Hallo, ich bekomme immer Optimal objective -0.000000000e+00, woran kann das liegen?
Hatte dasselbe Problem. Du must deine Datei vorher speichern bevor du die Kalkulation durchlaufen lässt
Hast du deine objective function beim Variablenhinzufügen deklariert? Standardmäßig sind die Faktoren nämlich 0
Hat jemand einen möglichen Lösungsweg für die Python Aufgabe gefunden? Ich bekomme das leider nicht richtig hin :(
Du versuchst am besten das Problem einmal auf dem Papier zu modellieren (wie in den Übungsaufgaben). Dann schaust du dir die Übungsfolien an, wo Python und Gurobi vorgestellt wird. Anhand der Beispiele dort kannst du die Aufgabe eigentlich ganz gut lösen (wobei natürlich etwas Programmier-Erfahrung das Ganze beschleunigen kann).
Könnte einer seine Lösung zur 'Christmas Market' Python Aufgabe posten? Wir wissen nicht so ganz wie die environment Constraint aussehen muss. wie definiert man Vtype, upper und lower bound bei der variablen Definition? Vielen Dank im Voraus :)
vtype=GRB.INTEGER, lower und upper Bound brauchst du eigentlich nicht (du kannst, musst aber nicht lb=0 setzen)
Für die environment constraint musst du zunächst über alle Personen iterieren und dann über ein IF abfragen, ob die aktuelle Person das Flag environment gesetzt hat. Falls ja iterierst du noch über alle Stände. Wenn der aktuelle Stand einen anderen "cup_type" als ceramic oder glass hat, fügst du eine constraint ein, die x_p,s auf 0 setzt.
Ich bekomme immer die Fehlermeldung "Undefined variable Model" oder "Undefined variable quicksum" bei der aktuellen programmieraufgabe, woran kann das liegen?
meinst du sowas hier? diese "pylint" fehler solltest du eigentlich ignorieren können und es sollte trotzdem alles laufen
Ja genau danke :)
Bei mir kommt immer für die Daten vom christmas_market-2018.py 262.796 anstatt der gesuchten 258.427 raus. Habt ihr eine Idee woran das liegen könnte?
View 1 more comment
Hast du bei den 2019er Daten auch ein falsches Ergebnis? So ein kleiner Fehler könnte bedeuten, dass deine Variablen nicht auf Integer (ganze Zahlen) beschränkt sind
Danke, Gaspumpe, daran lag es
Wann sind die nächsten Classtests?
nächsten Donnerstag und im Januar nochmal
19.12 10:30
Hi@all, I'm working on the second Python task "christmas market". I have two questions: 1) How to I implement the object function Sum over p∈persons Sum over s∈stands(xp,s*(alcohol content (s)/price(s)) in the code? 2) I don't know to come up with a solution for the environment constraint. Do I need to use If-loops? Can someone help? Thanks!
View 3 more comments
Hast du sowas erwartet wie if environment[p] == True? Da environment[p] ohnehin einen Wahrheitswert zurück gibt, braucht man das nicht mehr mit True zu vergleichen (True == True -> True, False == True -> False) ...
@Lukas Nadenau bekommst du damit den richtigen objective value raus?
Haben wir diese Woche den Test schon zurückbekommen? War leider krank..
View 3 more comments
Wo werden die Ergebnisse denn veröffentlicht? Bei uns im Tutorium wurde nur gesagt dass es die Tests nächste Woche gibt.
in moodle links unter bewertungen
Ab heute findet keine Vorlesung mehr statt oder?
ja
Wann kommt die nächste Gurobiaufgabe Online?
Frage ich mich auch... Abgabe soll ja schon morgen in einer Woche sein
9.12
Für die, die den Test nicht mitschreiben konnten (war echt ultra ez): 1a) Shops: L Friends: K Total Budget: J Limit for Shop l: O_l Maximum cups of wine for group: R u_{l,k}: Joy received from shop l for friend k u_l: Amount of wine per cup for shop l Maximize joy with the constaints b) Tina is the driver and cant drink (she is h\in K), add new constraint c) Hot chocolates are also available for the shops I \subset L. They give a joy for all. 2a) Customers p\in[k] Courses o\in[l] exacly N_p courses for each customer p the cost for a course happening is G_o u_{p,o} is the transportation cost for customer p attending course o minimize cost
wie viele Punkte braucht man die Klausur bestehen?
Vermutlich die Hälfte?!
50% wird normal nicht runtergesetzt, fällt ok aus. Das sind in dem Fall 30 von 60 Pkt
Könnte das möglicherweise jemand erklären? Also verstehe das mit dem Big M nicht, was das heißen/bringen soll und warum es dahin muss...
Es besteht die Möglichkeit, dass die Firma einen Zug länger als 50 m nutzen kann, das kostet sie den Preis o. An dieser Stelle wird diese Kapazitätsbegrenzung erfasst. Jetzt bestimmt yj bei wie vielen Zügen dies stattfindet. Jetzt zum M. Wäre das M z.B. nur 1 groß könnte das Produkt xij bi größer als das M werden, was es aber nicht soll, da wir uns über yj ja mehr an Kapazität erkauft haben. Das M muss entsprechend so groß sein, dass es die maximale Länge bi aller Waggongs übersteigt, denn hier soll es ja möglich sein, dass wir durch die zusätzlich erkaufte Kapazität im Sonderfall auch nur einen Zug mit alles an Waggonlänge schicken können was wir können.
No area was marked for this question
Bei 5.a: warum soll die Summe aller y = n sein? Reicht es nicht aus, das y = 1 ist?
da steht die summe aller xi
Macht Sinn :D
No area was marked for this question
I came up with the same solution as the one presented here. Problem: My optimal solution for Data1 is 6 and Data2 is 7. But tutOR says it should be 7 and 8. Does someone have the same problem?
View 1 more comment
für Data1
👍🏼
Hallo zusammen, im letzten Jahr wurden die Themen/Übungsblätter für die Tests eingegrenzt. Weiß jemand was dazu, ob dass dieses Jahr auch der Fall ist oder sind alle bisher gemachten Tutorien relevant? Danke!
Date: Dec 05, 2019IPlace: TEMP 2IStart: 10:30IDuration: 30 minutesITwo tasks, 18 and 12 minutes, respectively. Similar to examtasks. Scores indicate the expected time in minutes.IAllowed utilities: only black/blue ink and dictionaryIPlease know your tutor/tutorial!IAfter the test: short break & regular exerciseITopic: “assignment-like”,nojob scheduling, TSP, etc.
No area was marked for this question
Hello :) But how can you solve the problem with these? Isn´t there a missing model/ obj. fct? I don´t get it, I´m sorry.
View 1 more comment
Okay I understand that that part. But when I´m trying to "proof" the model, then the program "visual studio code" tells me that the model is undefined and there are several error notifications.
Maybe Gurobi isn't installed correctly... Does the code execute when you call "python3 binpacking-data1.py"
Wann genau ist der erste Class Test?
View 2 more comments
Je an der Übung. Danach kurz Pause.
gibts dazu ein Thema?
No area was marked for this question
Why do we need in the conlfict constraints the m? x[conflict[0],j] <= (1-x[conflict[1],j])*m The constraint would be already realised with m = 1 but it takes more simplex iterations 133 respectively 194 (m=1). The solution is the same.
Load more