DASH: dynamic approach for switching heuristics
From MaRDI portal
(Redirected from Publication:320816)
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.
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
Cites work
- scientific article; zbMATH DE number 1131473 (Why is no real title available?)
- scientific article; zbMATH DE number 7124428 (Why is no real title available?)
- A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
- A Computational Study of Search Strategies for Mixed Integer Programming
- A study of the lot-sizing polytope
- Active-constraint variable ordering for faster feasibility of mixed integer linear programs
- Algorithm portfolios
- Backdoor branching
- Branch-and-Bound Methods: General Formulation and Properties
- Branching rules revisited
- Flow pack facets of the single node fixed-charge flow polytope
- Heuristics for dynamically adapting propagation in constraint satisfaction problems
- Learning dynamic algorithm portfolios
- Learning value heuristics for constraint programming
- On the facets of the mixed-integer knapsack polyhedron
- Production Planning by Mixed Integer Programming
- SATzilla: portfolio-based algorithm selection for SAT
- The Accuracy of Search Heuristics: An Empirical Study on Knapsack Problems
- Valid inequalities for problems with additive variable upper bounds
Cited in
(7)- Configuring mixed-integer programming solvers for large-scale instances
- Machine learning for combinatorial optimization: a methodological tour d'horizon
- Deep learning assisted heuristic tree search for the container pre-marshalling problem
- \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
- Multivariable Branching: A 0-1 Knapsack Problem Case Study
- On learning and branching: a survey
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)
