Preference-Guided Tree Search for Feasible Solution Generation in Integer Linear Programming

Integer linear programming (ILP) arises in many critical decision-making tasks. While recent learning-based methods have shown promise in producing feasible solutions for ILPs, many rely on variable predictions that, on their own, do not necessarily yield high-quality solutions or even feasible solutions during inference. To address this gap, we propose a preference-guided tree search (PgTS) framework for high-quality feasible solution generation. Building on an underlying tree search that guarantees finding a feasible solution, PgTS jointly learns two guidance components to improve search efficiency and solution quality: reference values, which indicate preferred variable assignments, and variable ordering, which reflects the sequence in which variables are explored along the search. To align training with inference, PgTS evaluates each guidance pair through the same tree-search procedure used at inference, so that the learning signal directly reflects the quality of the resulting feasible solution. Based on the search outcomes, objective-based preference learning derives contrastive signals from their objective values to favor better guidance pairs, without requiring optimal-solution labels. Extensive experiments across ILP benchmarks show that PgTS achieves state-of-the-art solution quality and provides strong initial solutions that improve long-term solver performance over conventional and learning-based methods.