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 neighborhood around the current best solution. LNS relies on heuristics to select neighborhoods to search in. In this paper, we focus on designing effective and efficient heuristics in LNS for integer linear programs (ILP) since a wide range of COPs can be represented as ILPs. Local Branching (LB) is a heuristic that selects the neighborhood that leads to the largest improvement over the current solution in each iteration of LNS. LB is often slow since it needs to solve an ILP of the same size as input. Our proposed heuristics, LB-RELAX and its variants, use the linear programming relaxation of LB to select neighborhoods. Empirically, LB-RELAX and its variants compute as effective neighborhoods as LB but run faster. They achieve state-of-the-art anytime performance on several ILP benchmarks.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationSimilar Papers 제목 키워드 기반
Towards Optimal Branching of Linear and Semidefinite Relaxations for Neural Network Robustness Certification
In this paper, we study certifying the robustness of ReLU neural networks against adversarial input perturbations. To diminish the relaxation error suffered by the popular linear programming (LP) and semidefinite program…
Exploring the Power of Graph Neural Networks in Solving Linear Optimization Problems
Recently, machine learning, particularly message-passing graph neural networks (MPNNs), has gained traction in enhancing exact optimization algorithms. For example, MPNNs speed up solving mixed-integer optimization probl…
Combinatorial OptimizationA Unifying Complexity-Certification Framework for Branch-and-Bound Algorithms for Mixed-Integer Linear and Quadratic Programming
In model predictive control (MPC) for hybrid systems, solving optimization problems efficiently and with guarantees on worst-case computational complexity is critical to satisfy the real-time constraints in these applica…
Model Predictive ControlFeature selection in linear SVMs via a hard cardinality constraint: a scalable SDP decomposition approach
In this paper, we study the embedded feature selection problem in linear Support Vector Machines (SVMs), in which a cardinality constraint is employed, leading to an interpretable classification model. The problem is NP-…
Benchmarkingfeature selectionReinforcement Learning for Variable Selection in a Branch and Bound Algorithm
Mixed integer linear programs are commonly solved by Branch and Bound algorithms. A key factor of the efficiency of the most successful commercial solvers is their fine-tuned heuristics. In this paper, we leverage patter…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Variable Selection