Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning
Integer Linear Programs (ILPs) are powerful tools for modeling and solving a large number of combinatorial optimization problems. Recently, it has been shown that Large Neighborhood Search (LNS), as a heuristic algorithm, can find high quality solutions to ILPs faster than Branch and Bound. However, how to find the right heuristics to maximize the performance of LNS remains an open problem. In this paper, we propose a novel approach, CL-LNS, that delivers state-of-the-art anytime performance on several ILP benchmarks measured by metrics including the primal gap, the primal integral, survival rates and the best performing rate. Specifically, CL-LNS collects positive and negative solution samples from an expert heuristic that is slow to compute and learns a new one with a contrastive loss. We use graph attention networks and a richer set of features to further improve its performance.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationContrastive LearningGraph AttentionSimilar Papers 제목 키워드 기반
Local Branching Relaxation Heuristics for Integer Linear Programs
Large Neighborhood Search (LNS) is a popular heuristic algorithm for solving combinatorial optimization problems (COP). It starts with an initial solution to the problem and iteratively improves it by searching a large n…
Combinatorial OptimizationHyP-ASO: A Hybrid Policy-based Adaptive Search Optimization Framework for Large-Scale Integer Linear Programs
Directly solving large-scale Integer Linear Programs (ILPs) using traditional solvers is slow due to their NP-hard nature. While recent frameworks based on Large Neighborhood Search (LNS) can accelerate the solving proce…
Reinforcement LearningLearning to Search in Branch and Bound Algorithms
Branch-and-bound is a widely used method in combinatorial optimization, including mixed integer programming, structured prediction and MAP inference. While most work has been focused on developing problem-specific techni…
Combinatorial OptimizationImitation LearningStructured PredictionExploiting variable associations to configure efficient local search algorithms in large-scale binary integer programs
We present a data mining approach for reducing the search space of local search algorithms in a class of binary integer programs including the set covering and partitioning problems. The quality of locally optimal soluti…
ReLU Networks as Surrogate Models in Mixed-Integer Linear Programs
We consider the embedding of piecewise-linear deep neural networks (ReLU networks) as surrogate models in mixed-integer linear programming (MILP) problems. A MILP formulation of ReLU networks has recently been applied by…