4
$\begingroup$

The scenario is a game where each round you can buy or sell farms that make a set profit each round. I thought about applying branch-and-bound to a game tree, where each node represents the game state after each round, after buying/selling. The heuristic function I imagined is an estimate of how much money can be made "doing nothing from now" and in my case is an increasing function of depth. To my understanding, the branch-and-bound algorithm is, after initializing the queue with the initial game state, repeatedly pop a node off and branch if the bounded node heuristic value is better than an established lower bound (for a maximization problem).

From reading an overview of branch-and-bound, the bound is supposed to be a provable upper bound, but how can this actually be proved for a complex game? Instead, are the following simple bound methods I came up reasonable?

  • Compute the bound as the heuristic value discounted by a fixed fraction, say 0.8, to encourage exploring locally suboptimal branches. If the bound is simply set to the heuristic value at the node, is this simply a greedy search?
  • Instead of a fixed bounding function, consider best-first and limit the queue size to prevent considering too many nodes. But the runtime seems difficult to calculate to me as it's highly dependent on the structure of the tree and the order in which nodes are considered.

Also, if best-first is used with an increasing heuristic function, will this act like a depth-first search, since the first path chosen is increasing?

Improve this question
$\endgroup$
3
  • $\begingroup$ Normally the bound is found by solving a linear relaxation of your mixed integer model. The solution to the linear relaxation usually won't be feasible under the integer constraints (if it is, you can skip branching altogether), but its optimal cost will be at least as good as any feasible integer solution. $\endgroup$
    – Ben Voigt
    Commented Sep 16, 2022 at 19:55
  • $\begingroup$ @BenVoigt the bound is not necessarily computed by a linear relaxation. For example, for a graph coloring problem, a bound can be obtained by finding a clique $\endgroup$
    – fontanf
    Commented Sep 17, 2022 at 7:14
  • $\begingroup$ @fontanf: Sure, convex or other relaxations can also be used. But the linear relaxation is the most common, especially for one being introduced to the topic. $\endgroup$
    – Ben Voigt
    Commented Sep 19, 2022 at 14:45

1 Answer 1

Reset to default
6
$\begingroup$

A classical branch-and-bound is an algorithm used to prove optimality. In the end, all nodes have been explored. The bound is exact and is a critical component of the algorithm.

What you are looking for is not really a branch-and-bound algorithm, but rather just a "tree search" or "heuristic tree search" algorithm. In this case, we know in advance that there are to many nodes to be explored. Instead of looking for a bound to prune some nodes, we try to guide the search to explore in priority the regions of the search tree which look the most promising.

The subject is a bit too broad to explain everything here. Here are the slides of the class I teach about heuristic tree search, which should provide a good starting point.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.