UCLA

In this dissertation, I will cover two distinct topics. In the first part, I will discuss the subgraph isomorphism problem which has a broad range of applications from pattern recognition and bioinformatics to compilers circuit design. In combinatorial problems such as these, symmetry, if unaccounted for, can confound standard solvers leading to significant amounts ofredundant work being done. I will introduce multiple approaches for dynamically exploiting this symmetry to accelerate solvers as well as to compactly characterize the set of solutions. I rigorously establish conditions under which from one subgraph isomorphism, potentially exponentially many more may be generated. I also demonstrate through empirical assessment that incorporating symmetry into subgraph search can provide significant reductions in search time and produce many more solutions. In the presence of these huge solution spaces, there still remains the work of determining the actual subgraph isomorphism of interest. In an approach inspired by active learning, I will introduce the problem of querying template vertices for more information to uniquely identify solutions. Multiple different strategies for querying vertices which also incorporate symmetry are established and assessed by rigorous analysis and comprehensive experiments. In the second part, I will discuss methods for formulating neural network constrained optimization problems. With the advent of machine learning, neural networks have been used as a surrogate for complicated physical models, and the incorporation of these networks into optimization problems is a challenge. I will present a direct embedding approach, a mixed integer program, and a nonlinear program with complementarity constraints as methods for formulating these problems to be used with standard optimization solvers. I establish key properties of each methods, and through experiments, I assess the advantages and disadvantages for each approach.