  Current methods for solving Stochastic Shortest Path Problems (SSPs) find
states' costs-to-go by applying Bellman backups, where state-of-the-art methods
employ heuristics to select states to back up and prune. A fundamental
limitation of these algorithms is their need to compute the cost-to-go for
every applicable action during each state backup, leading to unnecessary
computation for actions identified as sub-optimal. We present new connections
between planning and operations research and, using this framework, we address
this issue of unnecessary computation by introducing an efficient version of
constraint generation for SSPs. This technique allows algorithms to ignore
sub-optimal actions and avoid computing their costs-to-go. We also apply our
novel technique to iLAO* resulting in a new algorithm, CG-iLAO*. Our
experiments show that CG-iLAO* ignores up to 57% of iLAO*'s actions and it
solves problems up to 8x and 3x faster than LRTDP and iLAO*.
