Beiträge von Enrico Bortoletto

    It's a pleasure to answer :)

    When doing graph optimization problems by hand there is no excuse for ignoring the obvious lower bound and continuing the branches all the way down. If I remember correctly, for bigger networks in branch-and-bound we normally need both a good heuristic/intuition to take the good decisions very early as well as a good (often non-trivial) lower bound to discard the bad decisions before branching almost all the way down.

    Branch and bound is a general solution strategy for any kind of discrete problem, not only for graph-based problems. It is first of all based on a branching rule, and if the branching rule is a good one it also has a bounding rule.

    • The branching rule is basically a rule that tells you what to change from a certain situation you have reached in order to get a new situation. After some branching, situation to situation, maybe you reach a situation that is also a solution to the problem. A necessary property of the branching rule is that you can prove that branching eventually stops (and maybe restarts somewhere else from another situation, and on and on, but eventually really stops). Another necessary property of the branching rule is that you can prove that if you branch everything then somewhere in your branchings you will have reached every possible situation. This is to ensure that whatever the optimal solution is, your branching rule is capable of bringing you there.
    • The bounding rule is a different thing, and evolves from what the branching rule allows. What do I mean? Sometimes your branching rule has the special property that going from a certain situation, say S, to a branching of S, say b(S), the "value" of b(S) is always less than the "value" of S. By this I mean that you can prove in general that branching always makes your situation worse. If this happens then you can start bounding things.

    How does the whole thing happen? Well, you start from some situation, and branch branch branch, until you find a situation that is a solution to the problem. You record the "value" of this solution and call it COV (current optimal value). You stop branching from this solution, because you have proved that branching only makes the "value" worse. You go now to some other situation you haven't fully branched down from, and branch branch branch while checking the values of the situations you find. Every time you reach a value that is worse than COV, you stop branching there, and start branching somewhere you haven't yet. If instead you find a situation that is also a solution, and its value is better than COV, then this becomes your new optimal candidate and you change COV to this new value.


    This strategy is the main strategy solvers use to do anything, together with of course smart heuristics and very refined ingredients. The base of it all is this, though.


    I had one course in which we used a solver for this kind of approach. It was a very interesting experience, but I often found it a bit annoying that most problems we did were done by "easy" modelling and then relying on the cleverness of the solver.


    I see! Modelling can seem easy at first, but it's definitely not so trivial after the initial examples.

    There are many problems for which several equivalent algebraic models are known, but only few of these models are fast enough for a solver to actually manage to solve things.

    Moreover there sometimes are problems that it is better to describe incompletely on purpose, and only perfect the description after some solving has already happened.

    Then there are problems for which changing basis of the space (if you do not know what a basis is, you can imagine it as just the "alphabet" with which you write vectors in a vector space) also changes the solving time by LOTS.

    Many things can happen by modelling things correctly (and incorrectly), and it's fun to study modelling in depth, or even specific models, as many semplifications and heuristics often arise there.

    Ich habe mir erlaubt, für die heutige Aufgabe durchzuprogrammieren... leider mit einer scheußlichen Laufzeit. Aber zum Glück war die Aufgabe nicht zu komplex und ich konnte sie schnell lösen. Aber bei größeren Datenmengen? Da wäre ich aufgeschmissen.


    Wahrscheinlich wäre ich ohnehin mit probieren schneller gewesen. Aber ich vertraue meinem Programm mehr als meiner Intuition 8o

    This is a very good approach, and I would be very interested to see your code (not in this forum, or else everyone else would have it). Remember that programming is not a shortcut, but a tool. If you are able to use it to get the answers you need and also understand the math within it, then you've just done a great great thing.


    The challenge here was not a simple one for a computer to brute force, even though it's about a network so very tiny. Through smart reformulations of the problem (the high dimensional geometric approach I spoke of above), together with very advanced heuristics and ideas (intuition!) there have been programs able to solve much, MUCH larger instances of similar problems. The key to these programs is 100% the math behind the reformulations though, because also most of the intuition implemented was coming from the geometric approach.


    Bravo for using a computer to solve things :)

    Ich stelle mir gerade die folgenden Fragen: Die Briefe sind leider ziemlich schwer und Steffan und Ralph möchten sie so kurz wie möglich tragen. Anstatt die Wegstrecke zu optimieren, wollen sie daher die Tragezeiten reduzieren, d.h., die Strecke, die sie einen Brief tragen müssen, summiert über alle Briefe. Welche Routen wählen sie nun? Macht es einen Unterschied, ob sie die Summe ihrer Tragezeiten minimieren wollen, oder nur die längere der beiden Tragezeiten?

    Very good ideas, and very good questions. What you are doing is changing the so called "objective function". There are some very easily resolved objective functions, there are some very hard to solve objective functions.


    What you are suggesting here (i.e. making the weight of a connection not constant, but dependent on an external variable instead (the amount of letters in the backpack)) is a strong complication to the problem. Very good thinking, it is much harder to solve now! These kind of problems, those where the data of your problem is not constant but depends on something else (usually time), are very hard optimization problems that are the central to modern day research.


    Nice question :)

    Ich finde in der Aufgabe nur die Angabe, dass die Rucksäcke je 143 Briefe fassen, aber nicht, wieviele Rucksäcke jedes Wichtel hat. Also: Wieviele Rucksäcke hat jedes Wichtel zur Verfügung?

    As you could expect, and as you can see in "Of course, to pick up letters they need to have sufficient space in their backpack.", there is only one backpack per elf. That is because elves only have two shoulders.

    Hallo, kann es sein das die zu wenig Arbeit für zu viele Wichtel haben? EInige der Aufgaben scheinen mir stumpfe Arbeitsbeschafungsmaßnahmen zu sein. Bspw. das sie Wurmlöcher benutzen, aber immer noch keine (automatische) Eisenbahn für die Post haben. Das scheint mir nicht auf die optimale Erledigung der Arbeit, sondern auf die Beschäftigung der Wichteln abzuzielen. Ein weiteres Indiz wäre die Langweiligkeit der Tätigkeit.


    Ist das der Fall?

    Hehe, social problems are NP-hard.

    Ich habe drei Fragen:

    1) Da ich in der Aufgabe nichts Gegenteiliges gefunden habe, gehe ich davon aus, dass nur die Zeit um den Weg zwischen den Postämtern berücksichtigt werden muss, das Einsammeln der Briefe selber aber keine Zeit verbraucht (und der Besuch der Cousine in Aussage a ebenfalls keine Zeit verbraucht). Stimmt das so?

    2) Aussage a ist so zu verstehen, dass Ralph zu einem beliebigen, bzw einem zu ihm günstigen Zeitpunkt zu Postamt 3 fahren kann, nicht dass er dort gleichzeitig mit Steffan ankommen muss. Stimmt das so?

    3) Aussage a impliziert für mich, dass Postamt 3 nicht ohnehin auf Ralphs Weg liegt, sondern auch tatsächlich ein Umweg wäre. Stimmt das so?

    Yes, yes, no.

    frank.buchholz schrieb:

    ... Plausibilitätsüberlegungen ...


    What is often interesting is seeing how different people use different intuitive claims to reach the same solutions. If you look at your intuition more and more closely you are often able to dissect it into different intuitive statements that are true by themselves. Then these simpler statements can sometimes be easily generalized (sometimes not so easily) to "rules of thumb" that often greatly help us find solutions, for example telling you what to start looking at first.


    frank.buchholz schrieb:

    Wie würde ein Computer so eine Übersicht mit einem Blick bekommen? Oder würde er stumpfsinning viele Routen durchrechnen und dabei manches durch clevere Progammierung abkürzen?



    A computer would typically solve this problem in a completely different way, by transforming it into a different problem. It would describe it as a special solid shape in very high dimension, and then explore this shape to find the solution somewhere on the boundary. This can sound very counter-intuitive, but after a while working with these things the relationship between combinatorial problems and algebraic-geometric interpretations becomes much clearer.

    Would the computer be able to get an overview at a glance? No. Computers do not glance 8o For it to "see" certain "intuitive" properties, those have to be explicitly coded into it, which is why we need to do what I was saying in the first paragraph: to know what our intuition tells us mathematically.

    frank.buchholz schrieb:

    Inzwischen scheinen verschiedene Projeke (Alpha Go, Schach, usw.) zu zeigen, dann KI-Anwendungen zum Lösen von komplexen Aufgaben eben keine Tipps oder Vorgaben von uns benötigen.


    This is true and false. The whole purpose of AI is to let it guess its own intuition, without us having to code it inside it. But how is this done? By "training" the AI, and this often takes a LOT of time. Sometimes MUCH more than the time you need to understand the intuition yourself and code it in by hand ;)

    AI is good for applications so complex that we fail to be intuitive with them, or where our intuition is even wrong.


    Great question! Thanks!

    Bei dieser Aufgabe hatte ich entweder ein Riesenglück oder aber eine gute Intuition: [...] Jetzt bin ich gespannt auf die Herleitung im Lösungsheft.

    This is very good! Try thinking what you would tell a computer if you wanted to teach it how to solve this kind of problems in general, for maybe much larger networks, or with many more elves. There are straight-forward solution strategies, but oftentimes it is also better to use what you used: intuition! But then...what is intuition? And how do you teach it? And how do you teach it to a computer???

    It's possible, sometimes, a little bit :)

    einem Branch-and-Bound-Ansatz verleiten (der dann oft in Branch-everything ausartet)

    When branch-and-bound becomes branch-everything it means that you are not actually doing the bounding part. A key component of b&b is that you are able to prove that all of the branching under a certain node will not be better than the solution at that node. Therefore then you can avoid exploring a certain branching of the search-tree if you have already found a feasible solution that is better than the solution at the root of that branching.

    Ist NP vollständig?

    I hope you are okay with some English.

    This question is complicated. It requires a longer preamble to be asked, and also to be answered. Any single challenge itself doesn't really belong to complexity classes (such as P, NP, NP-hard, NP-complete, Co-NP, etc.). Instead types of challenges, which we can call problems, can belong to certain complexity classes.

    To start answering this question, we would first need to specify which type of challenge we are talking about. Which problem this is.


    Example: the shortest route from Berlin to Venice is a single challenge, and doesn't really have a complexity class. The type of this challenge is the Shortest-Path-Problem on a euclidean graph, which certainly has a complexity class instead. The difference here is that the first one has a single answer, whereas the second one requires a generalized solution strategy.


    Later on, when this challenge isn't so fresh, we will be able to tell you more about this whole thing :D