DASH: dynamic approach for switching heuristics
From MaRDI portal
Publication:320816
DOI10.1016/J.EJOR.2015.08.018zbMATH Open1346.90629arXiv1307.4689OpenAlexW2151159522MaRDI QIDQ320816FDOQ320816
Authors: Giovanni Di Liberto, Serdar Kadioglu, Kevin Leo, Yuri Malitsky 
Publication date: 7 October 2016
Published in: European Journal of Operational Research (Search for Journal in Brave)
Abstract: Complete tree search is a highly effective method for tackling MIP problems, and over the years, a plethora of branching heuristics have been introduced to further refine the technique for varying problems. Recently, portfolio algorithms have taken the process a step further, trying to predict the best heuristic for each instance at hand. However, the motivation behind algorithm selection can be taken further still, and used to dynamically choose the most appropriate algorithm for each encountered subproblem. In this paper we identify a feature space that captures both the evolution of the problem in the branching tree and the similarity among subproblems of instances from the same MIP models. We show how to exploit these features to decide the best time to switch the branching heuristic and then show how such a system can be trained efficiently. Experiments on a highly heterogeneous collection of MIP instances show significant gains over the pure algorithm selection approach that for a given instance uses only a single heuristic throughout the search.
Full work available at URL: https://arxiv.org/abs/1307.4689
Recommendations
- Dynamic control in real-time heuristic search
- Heuristics for dynamically adapting propagation in constraint satisfaction problems
- Dynamic Management of Heuristics for Solving Structured CSPs
- A survey of hyper-heuristics for dynamic optimization problems
- Metaheuristics for dynamic combinatorial optimization problems
- Dynamic dominating set and turbo-charging greedy heuristics
- Heuristic allocation based on a dynamic programming state-space representation
- New heuristic for the dynamic layout problem
- A dynamic reformulation heuristic for generalized interdiction problems
Approximation methods and heuristics in mathematical programming (90C59) Mixed integer programming (90C11)
Cites Work
- A Computational Study of Search Strategies for Mixed Integer Programming
- A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
- Production Planning by Mixed Integer Programming
- On the facets of the mixed-integer knapsack polyhedron
- Branching rules revisited
- SATzilla: portfolio-based algorithm selection for SAT
- Algorithm portfolios
- Learning dynamic algorithm portfolios
- Heuristics for dynamically adapting propagation in constraint satisfaction problems
- Branch-and-Bound Methods: General Formulation and Properties
- A study of the lot-sizing polytope
- Backdoor branching
- Title not available (Why is that?)
- Title not available (Why is that?)
- The Accuracy of Search Heuristics: An Empirical Study on Knapsack Problems
- Learning value heuristics for constraint programming
- Flow pack facets of the single node fixed-charge flow polytope
- Valid inequalities for problems with additive variable upper bounds
- Active-constraint variable ordering for faster feasibility of mixed integer linear programs
Cited In (7)
- Configuring mixed-integer programming solvers for large-scale instances
- Machine learning for combinatorial optimization: a methodological tour d'horizon
- On learning and branching: a survey
- Deep learning assisted heuristic tree search for the container pre-marshalling problem
- Multivariable Branching: A 0-1 Knapsack Problem Case Study
- \textsc{Ner4Opt}: named entity recognition for optimization modelling from natural language
- Optimal decision trees for feature based parameter tuning: integer programming model and VNS heuristic
Uses Software
This page was built for publication: DASH: dynamic approach for switching heuristics
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q320816)
