UC Irvine

This dissertation develops Generative Problem Solving (GPS), a methodology proposed to bridge classic and modern AI, in which problem instances are generated from formal specifications and solved with procedures whose correctness is established in advance. Four instantiations are presented. GPS-Reasoning synthesizes logically consistent reasoning puzzles from random abstract syntax trees and templates over a first-order vocabulary. The generation procedure provides correctness and success-probability guarantees, and the resulting corpus is used to compare large language models with symbolic reasoning engines. GPS-SP organizes shortest-path constraints into five categories according to how they can be enforced during search, pairs each category with a dedicated solver under a strategy selector, and proves correctness and optimality for single and combined categories; experiments evaluate graphs of increasing size and show higher valid-solution rates and lower runtime than the LLM baseline. Extending GPS-SP from single-pair queries, the set-to-set instantiation formalizes constrained set-to-set optimization, in which an optimal subset of one entity set is selected with respect to another under path constraints, and characterizes the computational complexity and approximation guarantees of this problem family. The final instantiation applies the generative pattern to association rule learning under item hierarchies. H-SARL extends the Scalable Association Rule Learning (SARL) framework with category-aware edge-weight adjustment and weight-aware balanced partitioning. Its computational complexity is compared with top-down and bottom-up multi-level mining approaches. For the reverse problem, the dissertation defines a hierarchical consistency metric and formulates an exact integer linear program. Six approximate generation methods are also evaluated, including color-guided item selection, hierarchical block ILP, graph-cut generation, and a hierarchical genetic algorithm. Across the four instantiations, problem generation is coupled with domain-specific solution procedures, allowing both the generated problem space and the behavior of the corresponding solvers or miners to be studied formally.