Python Forum

Full Version: Branch and Bound
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
I am trying to learn about branch and bound. I understand the concept but have not had any luck tracking down an example of the code that works for what I want to do.

Say I have some letters ABCDEFG and I want to do every possible permutation. I know how to do that with itertools.

However, suppose some permutations are not allowed. For example, suppose I say that B is never allowed to come immediately after A.
To save computing time, I want to stop trying all the branches after this occurs. So all of the AB??? Permutations would never even be tried.

How can I write something like this please?
Maybe point me to an article? I can't find much that says how to stop the branch and go to the next one etc.

Thanks in advance.
This isn't really a branch and bound problem. Branch and bound is looking at optimizing combinations with respect to some evaluation function. It's meant to avoid an exhaustive search. You want an exhaustive search, just with some limits.

For your example, you would just do a tree search of all the permutations, and just not follow branches that ended in 'AB'.
(Jul-26-2018, 04:43 PM)ichabod801 Wrote: [ -> ]This isn't really a branch and bound problem. Branch and bound is looking at optimizing combinations with respect to some evaluation function. It's meant to avoid an exhaustive search. You want an exhaustive search, just with some limits.

For your example, you would just do a tree search of all the permutations, and just not follow branches that ended in 'AB'.

Explains why I can't find what I am looking for :) Should I look into Tree Search instead? How do I "not follow a branch"? What kind of commands should I look up? Thanks so much.
Permutations can be done with recursion:

def permutations(sequence, start = []):
    if not sequence:
        return [start]
    else:
        perms = []
        for item in sequence:
            new_sequence = sequence[:]
            new_sequence.remove(item)
            perms.extend(permutations(new_sequence, start + [item]))
        return perms
You just need to add code blocking certain combinations when you recurse.
(Jul-26-2018, 05:18 PM)ichabod801 Wrote: [ -> ]Permutations can be done with recursion:

def permutations(sequence, start = []):
    if not sequence:
        return [start]
    else:
        perms = []
        for item in sequence:
            new_sequence = sequence[:]
            new_sequence.remove(item)
            perms.extend(permutations(new_sequence, start + [item]))
        return perms
You just need to add code blocking certain combinations when you recurse.

Just got done looking up search tree's but they are Binary and what I am doing is not. It also requires understanding of linked lists which I did not, so I looked those up. That required understanding of classes which I do not have a super strong grasp on but I have been working on that this afternoon. It seems like a lot of stuff to learn just to do something simple. This answer above, about using recursion and limiting it, that sounds much more like what I want to do. I don't really know how to write it. Could you make me a short example to study? Say to generate a list of permutations of 'ABC' but anything with BC (in that order) is not allowed and not added to the list?
If that takes too long, can you point me to a article that talks about how to write something like this?
I am not aware of any articles explaining how to do exactly what you want. And out philosophy here is more help people fix code than write code for people.

Why don't you try it out yourself. If it doesn't work out, come back and tell me exactly how it didn't work, and I will help you fix it. Since you seem a bit new, I would recommend reading up on recursion first, to make sure you understand the example I gave you.
I have been playing with your code example and figuring out what it does.I think I will be able to do that on my own. How do you add rules about disallowing certain perms? I can't write it because I have no idea where to even start. What commands to use. I am used to using itertools for my perms.

Edit:
I don't quite get the purpose of the start = [] and if not sequence return start (I do know what if not does and I think this has to do with when the sequence runs out of items?)

I also can't quite grasp the feedback loop perms.extend etc. I understand it uses the same function inside itself but having a hard time visualizing it.
(Jul-26-2018, 06:38 PM)jarrod0987 Wrote: [ -> ]I don't quite get the purpose of the start = [] and if not sequence return start (I do know what if not does and I think this has to do with when the sequence runs out of items?)

You build the sequences one item at a time. That is, one item each call of the function. Start is the sequence build so far. At the beginning, it hasn't built anything yet, so the default is to have it be empty. Note that when we make the recursive call, the second (start) parameter is start + [item].

Again, read up on recursion. That's what is going on in my example.