In one embodiment, a target bandwidth, a lower boundary constraint on bandwidth, and an upper boundary constraint on cost are configured on a path computation device. The device may then compute a set of paths that is within the lower bandwidth boundary and upper cost boundary constraints. If the set of paths contains one or more paths, the device may select a path having a bandwidth value that is closest to the target bandwidth. However if the set of paths contains no paths, the device may search amongst paths that violate either the maximum cost or minimum bandwidth limits, selecting the path closest to the violated constraint (e.g., whose combined violation is minimized). Also, a weighting factor may be configured to establish the relative importance for a cost violation in comparison to a bandwidth violation.