SRG: Score-based Relaxation-guided Generation for Mixed Integer Linear Programming
We propose Score-based Relaxation-guided Generation (SRG), a generative framework based on an approximate formulation of relaxation-guided stochastic differential equations (SDEs) for mixed-integer linear programming. SRG employs a Transformer-based score network that incorporates feasibility and optimality signals into score modeling, encouraging the learned generative model to place more probability mass on feasible, high-quality regions of the solution space. At inference time, SRG directly samples diverse candidate solutions from the learned score model without requiring any additional guidance module. These candidates are then used to construct compact trust-region subproblems for standard MILP solvers. Across multiple public benchmarks, SRG matches or improves upon the solution quality of the strongest learning-based baselines, with particularly strong gains in challenging candidate-generation settings. Moreover, SRG shows promising zero-shot transferability to unseen cross-scale and cross-problem instances, improving solver objectives and reducing search time in several cases through higher-quality initial candidates and compact trust-region search.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Convex mixed-integer optimization with Frank-Wolfe methods
Mixed-integer nonlinear optimization encompasses a broad class of problems that present both theoretical and computational challenges. We propose a new type of method to solve these problems based on a branch-and-bound a…
Learning-to-solve unit commitment based on few-shot physics-guided spatial-temporal graph convolution network
This letter proposes a few-shot physics-guided spatial temporal graph convolutional network (FPG-STGCN) to fast solve unit commitment (UC). Firstly, STGCN is tailored to parameterize UC. Then, few-shot physics-guided lea…
Sharp Hybrid Zonotopes: Set Operations and the Reformulation-linearization Technique
Mixed integer set representations, and specifically hybrid zonotopes, have enabled new techniques for reachability and verification of nonlinear and hybrid systems. Mixed-integer sets which have the property that their c…
Fast Switching in Mixed-Integer Model Predictive Control
We derive stability results for finite control set and mixed-integer model predictive control with a downstream oversampling phase. The presentation rests upon the inherent robustness of model predictive control with sta…
Model Predictive ControlSolver-Verified Formulation Generation and Selection for Multi-Warehouse Inventory Allocation Using Large Language Models
Balance-oriented multi-warehouse inventory allocation is a recurring decision problem in large-scale e-commerce supply chains, in which a fixed replenishment quantity is distributed across warehouses to balance post-allo…