AI 與世界的難題 · 理論資訊科學 · arXiv · 2026-10-22
以遺傳規劃進行混合整數線性規劃之可解釋切割平面選擇
原標題: Interpretable Cutting Plane Selection for Mixed-Integer Linear Programming Using Genetic Programming
割平面是混合整數線性規劃(MILP)求解器的關鍵要素,但目前的手工切割策略是靜態的,而以神經網路為基礎的學習式策略可解釋性有限,且不保證收斂。作者提出 GPSCS,這是首個將手工啟發式方法泛化為完全可解釋策略的學習式框架:基因規劃演化出一個為候選切割排序的符號評分函數,並由輕量的統計機制自適應地決定每個分離回合要加入多少個排名最高的切割。在 SCIP 中以七類合成與真實世界基準進行評估,其評估實例平均比訓練實例難41倍,GPSCS 相較 SCIP 預設方法將平均求解時間改善6%,並相較近期神經網路方法與無切割基準皆達到兩倍的加速。