We consider the problem of identifying solutions to a stochastic system under multiple constraints. The objective function and the constraints are expressed in terms of performance measures of the system that are observable only via a simulation model parameterized by a finite number of decision variables. In solving for such a system, one faces the much harder challenge of verifying the feasibility of a potential solution. Toward this, we present cgR-SPLINE, a multistart simulation optimization (SO) algorithm on integer spaces. cgR-SPLINE sequentially solves random restarts of a gradient-based local search routine with increasing precision. The local search routine in turn solves progressively stricter outer approximations of the underlying problem. The local solution estimator from a recently ended restart is probabilistically compared against an incumbent solution, thus generating a sequence of global solution estimators. The optimal convergence rate of the solution iterates is observed to be sub-exponential, slower than the exponential rate observed for SO problems on unconstrained discrete spaces. Additionally, efficiency for cgR-SPLINE dictates that the number of multistarts and the total simulation budget be sublinearly related, implying an increased emphasis on exploration than is prescribed in the continuous context. Heuristics for choosing constraint relaxations and solution reporting demonstrate good finite-time performance on three SO problems, of which two are nontrivial. The extension of cgR-SPLINE's framework to mixed spaces seems a natural next step. The presence of infeasible points arbitrarily close to the stochastic boundary, however pose challenges for consistency. We present a general framework for mixed spaces that is very much along the lines of cgR-SPLINE and propose ideas for specific algorithmic refinements and solution reporting. Strategically locating the restarts of a multistart SO algorithm appears to be a largely unexplored research topic. Toward achieving efficiency during the exploration phase, we present ideas for ``antithetically" generating the restarts from probability measures constructed from the SO algorithm's performance trajectory. Asymptotic behavior of the proposed sampling strategy and policies for optimal parameter selection are presently conjectural, but appear promising based on the outcomes of preliminary experiments. / Ph. D.