Dynamic Approach for Switching Heuristics
Dynamic Approach for Switching Heuristics
复制标题
切换启发式的动态方法
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Y. Malitsky
中科院分区：
文献类型：
--
作者：
Y. Malitsky
搜索是NP-hard组合优化和决策问题求解方法的重要组成部分。一旦确定性推理的能力被耗尽，最先进的求解者就会尝试可能导致改进（在优化的情况下）或可行（在令人满意的情况下）解决方案的替代方案。这种对备选方案的考虑可能是高度机会主义的，如在本地搜索方法中，也可能是系统地，如在基于回溯的方法中。无论在什么情况下，如果能够有效地支持导致最优或可行解决方案的替代方案，以及允许对最优性或不可行性进行简短证明的搜索空间分区，那么效率都可以大大提高。因此，本章将继续讨论基于当前子问题的某些特征动态选择分支启发式算法的想法，从而产生明显优于在整个搜索过程中只使用单一启发式算法的解决方案。
Search is an integral part of solution approaches for NP-hard combinatorial optimization and decision problems. Once the ability to reason deterministically is exhausted, state-of-the-art solvers try out alternatives that may lead to an improved (in case of optimization) or feasible (in case of satisfaction) solution. This consideration of alternatives may take place highly opportunistically, as in local search approaches, or systematically, as in backtracking-based methods. Regardless of the scenario, efficiency could be much improved if one could effectively favor alternatives that lead to optimal or feasible solutions and a search space partition that allows short proofs of optimality or infeasibility. The chapter therefore follows up on the idea of choosing a branching heuristic dynamically based on certain features of the current subproblem, resulting in solvers that are markedly better than their counterparts that stick to using only a single heuristic throughout the search.