Branching and lower bounds are two key notions in heuristic search and combinatorial optimization. Branching refers to the way the space of solution is searched, while lower bounds refer to approximate cost measures used for focusing and pruning the search. In Al Planning, admissible heuristics or lower bound have received considerably attention and most current optimal planners use them,either explicity or implicity (e.g by relying on a plan graph). Branching, on the other hand, has received less attention and is seldom discussed explicitly. In this paper, we make the notion of branching in planning explicit and relate it to branching schemes used in combinatorial optimization. We analyze from this perspective the relationship between heuristic-search, constraint-based and partial-order planning, and between planning and scheduling. We also introduce a branch-and-bound formulation for planning. The goals are twofold: to make sense of various techniques that have been found useful in planning in a unified framework, and to lay the ground for systems that can effectively combine recent advances with schedulin capabilities. We have also implemented planner based on this formulation on top of a constraint programming lenguage and present results.