This paper proposes RIDGECUT, a novel framework for applying reinforcement learning (RL) to combinatorial optimization problems, specifically the Normalized Cut problem. To address the difficulty of incorporating domain knowledge, a limitation of existing RL-based methods, we propose a method that leverages domain knowledge to constrain the action space. Using an urban road network as an example, we transform the graph into a linear or circular structure using concentric and radial road structures, and perform efficient learning using sequential transformers. As a result, we achieve lower Normalized Cut values than existing methods and generate partitions that closely align with the spatial layout. While this research focuses on traffic data, we provide a general mechanism for incorporating structural prior knowledge about graph partitioning problems into RL.
