Branch and Bound Methods

In this post, I would be talking about branch and bound methods, and implementing an approach tailored for a specific AGV scheduling.

Useful Links and resources:

• This Gurobi website for basic concepts and terminologies.

Interesting insights and concepts:

In this section, I’ll provide some interesting insights or challenging concepts regarding the B&B methods.

Basic concepts

• Def of Incumbent: The best integer solution found at any point in the search. [Gurobi website]

A special of category of B&B algorithms: Alpha-Beta pruning

• In this search algorithm, there are two bounds, namely \(\alpha\) and \(\beta\), each are defined to be the minimum (maximum) reward that the maximizing (minimizing) player is assured of. Whenever, \(\alpha > \beta\), that branch is pruned.

Below is the Pseudo code of the alphabeta pruning:

---

function alphabeta(node, depth, α, β, maximizingPlayer) is
    if depth == 0 or node is terminal then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
            if value > β then
                break (* β cutoff *)
            α := max(α, value)
        return value
    else
        value := +∞
        for each child of node do
            value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
            if value < α then
                break (* α cutoff *)
            β := min(β, value)
        return value

---

• In the view of the Maximizing Player, this is always the case: value \(< \alpha\) as \(\alpha\) is always the α := max(α, value). Now, if the value \(> \beta\), it would imply that \(\alpha > \beta\). Now: in the context of B&B algorithm, it would mean that whenever the lower bound is greater than the upper bound of the node, then prune. How similar!!

• The use of Upper Bound (UB) as it is explained in this article, is correspond to \(\beta\) in alpha-beta pruning algorithm.</br> In B&B:

  \(\text{LB} > \text{UB} \Rightarrow \textbf{Prune!}\) </br>

  In alpha-beta pruning:

  \[\alpha > \beta \Rightarrow \textbf{Prune!}\]

---

QCSP article by Kim and Park (and improvements by Moccia2005)

Implementation insights:

• I used Cplex Concert C++ api, for the decision variables and solving the relaxed underlying MTSP in the B&B approach
• don’t use any IloCplex::solve() for the main model.

Classes:

• DecisionVariables.h
• Cplex Model Constraints –> for making improvements proposed by Moccia & et. al.
• C++ converted constraints –> for making feasible children!