Easy Callbacks

Some methods from Problem can be easily incorporated into BranchAndBound callbacks for useful operations.

So far, the two most relevant implemented are:

• Problem.primal_heuristic: Should also call BranchAndBound.primal_heuristic

• Problem.stronger_bound: Should also call BranchAndBound.upgrade_bound

Primal Heuristics

These should return (if possible) a feasible solution from any part of the search tree and are wrapped in other Node and BranchAndBound methods. In the Permutation Flow Shop example, it is called every time a new solution is found, applying local search. In the machine weighted deadline problem, it is called (in the lagrangian-based formulation) from every node returning the Smith’s heuristic solution, which is used in bound computations.

from bnbpy import BranchAndBound, Node, Problem

On solution improvement

class SolutionImprovementBnB(BranchAndBound):
    def solution_callback(self, node: Node) -> None:
        self.primal_heuristic(node)


class ExampleProblem(Problem):
    def primal_heuristic(self):
        child = self.child_copy(deep=False)
        # Modify child to be a feasible solution
        # better than the current one
        return child

During the search tree

class PrimalSearchBnB(BranchAndBound):
    def post_eval_callback(self, node: Node) -> None:
        self.primal_heuristic(node)


class PrimalHeuristicProblem(Problem):
    def primal_heuristic(self):
        child = self.child_copy(deep=False)
        # Modify child to be a feasible solution
        return child

Bound Improvements

Some bound computations can be expensive therefore can be delayed on demand. To do so, trigger on demand during the search tree the upgrade_bound method for problems with a stronger_bound implementation called right after bound computation.

class MyImprovingBoundBnB(BranchAndBound):
    def post_eval_callback(self, node: Node) -> None:
        # You don't need to always call it
        # you can decide to call it only when the node is promising
        # Maybe also depending on the depth of the node, or other factors
        if node.lb < self.ub:
            self.upgrade_bound(node)


class ProblemWithExpensiveBound(Problem):
    def stronger_bound(self):
        # Do something expensive to compute a better bound
        return self.solution.lb * 0.5