The global terrain methodology of Lucia and Yang (2003) is a method for finding multiple solutions to optimization problems that is based on the fact that stationary points (i.e., saddle points and minima) and singular points are generally connected along smooth valleys on the objective function surface. In this presentation, we show that there are cases where not all stationary and singular points to optimization problems necessarily lie in the same valley and that these valleys are not necessarily smoothly connected. Accordingly, logarithmic barrier functions are used to create smooth connections between distinct valleys so that the global terrain method is guaranteed to explore the entire feasible region. Once valleys are connected, different stationary and singular points in separate parts of the feasible region can be calculated, identified or characterized, and sequentially tracked as the barrier parameter is reduced. The proposed barrier-terrain methodology is used to successfully find all physically meaningful solutions to a number of small illustrative examples and a collocation model for a spherical catalyst pellet problem with 20 variables. The key contributions of this work are the discovery that barrier methods provide connections between valleys containing stationary points for intermediate barrier parameter values under mild conditions on the model equations and the robustness of the proposed barrier-terrain method. Many geometric illustrations are used to highlight key features of the barrier-terrain approach.