Node selection

Find a good integer solution?

-or-

Prove no solution with smaller objective value than zbest exists?

• Best-first (Best-bound) search

  • Choose the one with smallest value zk
  • For fixed branching rule, this minimizes search tree
  • Focus on improving global lower bound
  • Little pruning can mean large memory requirements
  • Tends toward “breadth-first” so that subsequent subproblem unrelated
    • More time spent evaluating the nodes

• Depth-first

  • Lower memory requirements
    • Subsequent problems highly related (bound change), so less time spent evaluating the nodes
  • Find feasible solutions more quickly
  • Large search trees

• Choose based on node “likely” to lead to good integer solution

  • “Best project”, “Best estimate”

• Choose different strategies at different points in the search

• Solvers give you the power to direct the node selection

Previous slide

Next slide

Back to first slide

View graphic version