Design and Implementation of an Heuristic-Enhanced Branch-and-Bound Solver for MILP
We present a solver for Mixed Integer Programs (MIP) developed for the MIP competition 2022. Given the 10 minutes bound on the computational time established by the rules of the competition, our method focuses on finding a feasible solution and improves it through a Branch-and-Bound algorithm. Another rule of the competition allows the use of up to 8 threads. Each thread is given a different primal heuristic, which has been tuned by hyper-parameters, to find a feasible solution. In every thread, once a feasible solution is found, we stop and we use a Branch-and-Bound method, embedded with local search heuristics, to ameliorate the incumbent solution. The three variants of the Diving heuristic that we implemented manage to find a feasible solution for 10 instances of the training data set. These heuristics are the best performing among the heuristics that we implemented. Our Branch-and-Bound algorithm is effective on a small portion of the training data set, and it manages to find an incumbent feasible solution for an instance that we could not solve with the Diving heuristics. Overall, our combined methods, when implemented with extensive computational power, can solve 11 of the 19 problems of the training data set within the time limit. Our submission to the MIP competition was awarded the "Outstanding Student Submission" honorable mention.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition
We improve the scalability of Branch and Bound (BaB) algorithms for formally proving input-output properties of neural networks. First, we propose novel bounding algorithms based on Lagrangian Decomposition. Previous wor…
Adversarial RobustnessGPUThe Hybridization of Branch and Bound with Metaheuristics for Nonconvex Multiobjective Optimization
A hybrid framework combining the branch and bound method with multiobjective evolutionary algorithms is proposed for nonconvex multiobjective optimization. The hybridization exploits the complementary character of the tw…
Evolutionary AlgorithmsMultiobjective OptimizationImproving Learning to Branch via Reinforcement Learning
Branch-and-Bound~(B\&B) is a general and widely used algorithm paradigm for solving Mixed Integer Programming~(MIP). Recently there is a surge of interest in designing learning-based branching policies as a fast approxi…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)A Parallel Monte-Carlo Tree Search-Based Metaheuristic For Optimal Fleet Composition Considering Vehicle Routing Using Branch & Bound
Autonomous mobile robots enable increased flexibility of manufacturing systems. The design and operating strategy of such a fleet of robots requires careful consideration of both fixed and operational costs. In this pape…
A Learning based Branch and Bound for Maximum Common Subgraph Problems
Branch-and-bound (BnB) algorithms are widely used to solve combinatorial problems, and the performance crucially depends on its branching heuristic.In this work, we consider a typical problem of maximum common subgraph (…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)