The algorithm below solves a 4 queen puzzle: put 4 queens on a 4 by 4 board and make sure they can't attack each other.

It is an improvement over brute force. It starts with an empty chess board and explores the most promising branches first. Based on the first initialized solution it comes across, it can prune away all branches who's partial solution doesn't violate less constraints.

algorithm

Someone once told me this algorithm is named Branch and Bound. Is that correct? If that's wrong, what is the real name of this algorithm?

asked 04 Sep '12, 10:05

Geoffrey%20De%20Smet's gravatar image

Geoffrey De ... ♦
3.6k42765
accept rate: 6%


The "Bound" part of branch-and-bound, to me, implies a upper bounding function (for a maximization), also known as a relaxation. "Standard" integer programming branch and bound uses the linear programming relaxation, but any relaxation can provide an upper bound and hence be put in branch-and-bound (there are lots of papers on "branch and bound" that use other relaxations). Here, the "objective" is -(number of conflicts), and the relaxation is based on the idea that "adding queens can only add conflicts" (so once k queens are fixed, the number of conflicts for those gives a bound on any completion). So you might call it branch-and-bound.

Given the fact you are only trying to find feasibility and given the simplicity of the bound, I would be more likely to call this backtracking depth-first search.

link

answered 04 Sep '12, 14:03

Michael%20Trick's gravatar image

Michael Trick ♦♦
4.1k51633
accept rate: 20%

edited 05 Sep '12, 03:36

Geoffrey%20De%20Smet's gravatar image

Geoffrey De ... ♦
3.6k42765

Does "backtracking depth-first search" imply the pruning technique shown above? If not, is there a finer grained term that does imply the pruning technique?

(04 Sep '12, 14:21) Geoffrey De ... ♦
1

This prunes as soon as it hits infeasibility (unless the diagram is supposed to show something else): that is the backtracking part. Note that all the "-1" and "-2" could just as well be "infeasible": the values don't have any relevance other than to denote infeasibility.

(04 Sep '12, 14:25) Michael Trick ♦♦
1

Adding to @Michael Trick's comment, 'pruning' in BnB is sometimes/usually called 'fathoming'. I hear 'pruning' used alot more in the AI community (eg. RN's textbook) to refer to more advanced techniques in constraint propagation, etc.

(04 Sep '12, 21:58) yeesian
2

I think "backtracking search" is fine if it incorporates pruning of any sort (or no pruning at all). I tend to agree that "branch and bound" best describes the case where bounds on an objective function are driving the pruning operations. Here, the objective is rather artificial, representing a measure of infeasibility. So in a technical sense, "branch and bound" is correct, but "backtracking" is probably less likely to provoke the pedants.

(04 Sep '12, 23:35) Matthew Salt... ♦

@Michael There's a small variation on what the diagram is suppose to show: as soon as a full solution (= solution with all queens on the chessboard) is found, it sets a minimum bound. For example, index 14 gives a solution of -1. Therefore, anything <= -1 can be pruned. This works for soft constraints as well as hard constraints, so it's more than just about "infeasibility". On the other hand, it only works when there are only negative constraints.

(05 Sep '12, 02:29) Geoffrey De ... ♦
1

Yes, if your objective is to find a minimum conflict solution (without assuming a no conflict solution is possible) then the bound becomes much more relevant, and becomes much more "branch and bound" (in my view).

(05 Sep '12, 16:10) Michael Trick ♦♦

Interesting: it doesn't work as soon as there are positive constraints (constraints that award a pattern, instead of punishing it). For example: score + 1 if 2 queens are a knight's jump away from each other. Any other type of constraints that would break it?

(06 Sep '12, 03:37) Geoffrey De ... ♦

Fixed. Thanks!

(07 Sep '12, 07:49) Geoffrey De ... ♦
showing 5 of 8 show 3 more comments

I believe the term "branch-and-prune" is up coming to characterize these kinds of algorithms (see here). Although the line between "branch-and-bound" and "branch-and-prune" is blurry as one might consider cutting planes as a form of pruning.

link

answered 04 Sep '12, 20:48

Carleton's gravatar image

Carleton
29214
accept rate: 0%

edited 05 Sep '12, 00:55

Ehsan's gravatar image

Ehsan ♦
4.8k31122

1

For the time being, you should avoid posting with direct links in them. Use the link button in the formatting toolbox instead.

(05 Sep '12, 01:20) Ehsan ♦

The phrase "partial enumeration" was (still is?) used to describe algorithms that (implicitly or explicitly) expand the solution space into an inverted tree but prune some branches. It is intended to contrast with "full enumeration" of course evaluates every feasible candidate in the solution space. The algorithm in the question clearly is a partial enumeration algorithm; whether the phrase is sufficiently specific is another question.

link

answered 05 Sep '12, 11:00

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k513
accept rate: 19%

Yea, I've heard the name 'implicit enumeration' mentioned as a special case of BnB applied to binary integer programs, described the way Geoffrey did.

(05 Sep '12, 11:23) yeesian

Quoting the Wikipedia page about Branch-and-Bound :

A branch-and-bound algorithm consists of a systematic enumeration of all candidate solutions, where large subsets of fruitless candidates are discarded en masse, by using upper and lower estimated bounds of the quantity being optimized.

In your example (if I get the things right) you are tackling a satisfaction problem by minimizing an objective function equal to the sum of the number of violated constraints, and you consider "a priori" that a feasible solution exists as you discard all partial solution having a score < 0.

So IMO it is ok to call this algorithm a Branch-and-Bound, I may be wrong but I think that this term is also used in the CP community even when solving CSP.

link

answered 04 Sep '12, 10:33

Renaud's gravatar image

Renaud
60517
accept rate: 8%

Hmm, so I haven't been embarrassing myself by calling this algorithm Brand and Bound for ages in my manual? ;) Despite Wikipedia's definition, this had me worried for some time, as I think I saw it coming up in Cook's TSP book in a very different context.

(04 Sep '12, 10:44) Geoffrey De ... ♦

Looks like "backtracking depth-first search" is probably more appropriate as the integer programming puts a dip on the term "Branch and Bound". Maybe we should update Wikipedia?

(05 Sep '12, 03:02) Geoffrey De ... ♦

I think it's more likely to be termed Backtracking (for constraint satisfaction problems)? With some heuristics (on the order in which you should try each branch) thrown in. Here's a nice survey (link) of such algorithms for Constraint Satisfaction Problems (CSPs) in AI.

I have heard of the term 'Branch-and-bound' used only in integer programming thus far, and not so much in the AI community. Your original description of the problem didn't reformulate the problem as an optimisation problem, so (imo) it seems more natural to view it as a 'search' algorithm.

link

answered 04 Sep '12, 10:45

yeesian's gravatar image

yeesian
846210
accept rate: 3%

edited 04 Sep '12, 11:14

1

To my best knowledge, BT & BnB are quite familiar concepts – but "usually" BT implies a certain kind of solution space exploration (depth-first traversal) and is applied "in-place"; BnB is more flexible/broad w.r.t. to applicable search strategies, branching rules, and explicitly leverages an auxiliary data structure to manage solution candidates. [Edit: Oh great... note to self: always refresh your browser before posting... – @Michael Trick's answer already made all "my" points, and did it in a better way.]

(04 Sep '12, 14:29) fbahr ♦
1

Oh okay, thanks for highlighting the nuances in the two algorithms. I agree that @Michael Trick's answer addresses it best. Sometimes our choice of names suggests ('gives hints to') the algorithm that we're actually running, and given the simplicity of @Geoffrey's original description, I don't think BnB is the first thing that jumps to mind (unless you can establish the equivalence between the algorithms, the way @Renaud and @Michael Trick did)

(04 Sep '12, 21:43) yeesian

Overlapping names for algorithms happens and is OK and I see the name connection. But in this case it's one of the most well known ones and for most people tightly connected to standard integer programming. If I were you, I would find a more unique suitable name, which will not cause so much confusion.

link

answered 04 Sep '12, 10:54

Bo%20Jensen's gravatar image

Bo Jensen ♦
5.0k2919
accept rate: 14%

Divide and explore ? (Not an expert so guessing in the dark here :-))

(04 Sep '12, 10:58) Bo Jensen ♦
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×29

Asked: 04 Sep '12, 10:05

Seen: 5,296 times

Last updated: 07 Sep '12, 07:50

OR-Exchange! Your site for questions, answers, and announcements about operations research.