We introduce multi-phase project planning (MPPP) as the problem of finding an executable sequence of sets of actions to achieve all hard subgoals of all milestones and achieve hard and soft subgoals optimally, using fully-specified initial state, milestones and their subgoals, preconditions and effects of operators, rewards and penalties associated achievement and cancellation of soft subgoals, rewards for earlier achievement of hard subgoals and specified events affecting the subgoals. We present a constraint-based approach to solving this problem.